My wife and I have tried a few solutions. I currently rely on taking a photo with my iPhone at the same time and using that photo’s data to position my “real” camera’s photo on Flickr (or, very recently, in Lightroom 4). Obviously, it’s far from an ideal solution.
My wife does a lot of travelling to out-of-the-way parts of the world that have poor coverage on online maps (particularly those on Flickr), which makes positioning photos tricky. After much frustration she tried one of the GPS trackers - the film-canister size ones - mentioned by others. She found it a pain to set up on a Mac and never had much success getting useful data to match up with photos. She soon stopped using it.
Eventually she upgraded her old camera and, after much reading of reviews, bought one of the few smallish cameras with built-in GPS, the Sony Cyber-shot DSC-HX9V: http://www.amazon.com/dp/B004HYFX0C/ She used it recently and it Just Worked - she uploaded photos to Flickr and, with no manual intervention, they were all positioned on the map.
While I’m keen to buy a new camera myself, I’m now thinking I should wait until the ones I want have GPS built in. Non-GPS-enabled cameras are starting to feel broken.