well they can do a best guess based on the location of your IP, even if you only sign into facebook once while you're travelling. The really interesting question is: can they do this even if you have not signed into facebook at all on your travels, or for totally new accounts with no location history at all.

If they can, then they must be doing image recognition in some way. Perhaps someone who has more time / energy than me could try this by creating a new account and uploading some photos of recognisable objects (but without exif geo data).