My theory about why Henry knows something is up, and why he hasn't changed, is because he was brought to Storybrooke from somewhere else and because Emma escaped the curse, he isn't a part of it either. He would change, and he would no doubt notice that nobody else does. Because he probably shares the trait with his mother where he can tell when someones lying, when he asks his adoptive mom about what's going on, he can tell she's not being truthful. I don't know how he figures out the whole Fairy tale thing though...and of course since the Lost people are involved in this, Henry probably is just dreaming the whole thing.
I'm sure I'm wrong, but when I watched the episode where Emma cuts up the Apple tree, I thought when she told Mr. Gold her name, that's when he remembered his old life. When Snow walks away from him in the Fairytale world he demands her name, so it must be very important for him to have. I was thinking that the name would be the key to his remembering after the curse took hold. That he knew she would come to the town and once he asked her name it would unlock his memories. Kind of like in Lost how they had to have an anchor (or something like that, Lost was very confusing, lol!) when they were traveling through time (or whatever it was they were doing) I was thinking Emma was Mr. Golds anchor.
I guess though that wouldn't explain how he found Henry...