I thought I could remember reading somewhere that passports weren't used that much during Victorian times - this article seems to explain why:

http://www.wanderlust.co.uk/magazine/articles/destinations/a...

Apparently rail travel made the whole process of issuing and checking passports a bit of a pain so most countries just gave up - they didn't become common again until 1914.