I don't remember for sure in the movies, but in the book, Gandalf tells Frodo a great deal of the tale of Smeagol while Frodo is still in the Shire. (He does this in the context of telling him about the Ring and its history, and why Frodo will have to leave for Rivendell or somewhere else.) Additionally, Gandalf tells the full story to the Council of Elrond at Rivendell, at which Frodo was present. So in the context of the book, Frodo always knew that Gollum was once a hobbit (not just "like a hobbit" but an actual hobbit), and always knew that Gollum had murdered his friend for the Ring and then fled to the caves of the Misty Mountains.
In the movies, Gandalf and Frodo have a discussion about Gollum as they're going through Moria. Presumably we only see a portion of this conversation and this is when Frodo learns the rest of Gollum/Smeagol's background.