If you stick on the roads you'd get away with thinner, slicker tyres which in turn will increase your speed a fair bit over an average. Having an idea on your route and what sort of surfaces you'll be riding on will be the best way to decide what tyres and bike to use, obviously if you use gravel toe-paths and muddy trails you won't be able to do it on 23c tyres, and likewise if you stick to all roads, doing it on 26x2.1 knobblies will be painfully slow (as in sub 10mph average).
Having a tent and cooking stuff adds up to a fair amount of weight so you'll probably be going for a full on tourer anyway. I'm not a tourer but I know a lot of people on here swear by bikes like the Dawes Galaxy.