Roflcopter already tackled the actual route planning more completely than I ever could. I thought I'd add a bit about the time you can expect to take.
This depends mainly on the following:
The amount of cycling you do in regular life
Regardless of how fit you are, your body needs to adjust to the cycling if you are not a regular cyclist. Plan trips of fewer km/day for the first week to 10 days, and add a few rest days if you are not at least a regular (50km/week+) cyclist. Your bum will become sore, obviously, but if your body is not used to prolonged bike sitting you will also feel this in your back, shoulders, neck and arms.
Your fitness level at the start of your trip:
Cycling is a physical activity. Even if you have no problem cycling 20km/h for 2 hours around your town you will find that cycling 15km/h for 5 hours is much more demanding, doing this a few days in a row even more so. Take a few test-trips of 5 hours or more in the weeks before you embark on your trip to find out how your body feels at the end of the day, and the day after. If you are tired at the end of the day, but feel fine the day after you have found a distance that you can keep up for more than a few days in a row.
The bike you ride
Get a bike that is suitable for the terrain you expect to tackle. In most cases slick road racing tires are not the best choice because they skid easily on loos gravel, sand, other dirt, or mud. If you plan on taking luggage, don't take your 8kg full carbon racer. Get a light-but-stiff mountain bike and fit it with narrow-but-not-too-narrow road tires, or get a hybrid or fitness bike fitted with these tires.
The amount of luggage you are planning to take
Full camping gear will weigh in at about 15-20 kg, if you plan on staying in hotels/hostels/b&b's you can cut this to below 10kg. This is dead weight that you will have to drag around all the time. In my experience full camping gear (which for me is about 17 kg) cuts my maximum daily distance by about 10-20% compared to no gear. Also, more gear might mean you need to take a stronger, heavier bike on your trip.
The amount of sightseeing you are planning to do
Don't expect to slog around a town looking at the sights after you've just spent 8 hours on your bike. If you want to do more than just take in the highlights from the saddle of your bike, plan accordingly. Plan half- days or even full days just for sightseeing.
So, now on to the actual numbers. I will try to outline a few steps to figure out a reasonable average speed. My base bicycle here is a reasonably light (~13kg) mountainbike or fitness bike, fitted with road tires with some profile (no slicks), and with 24 gears:
If you almost never cycle in your daily life (i.e. no commute, no long distance (30km+) recreational cycling on weekends, start with 12km/h.
If you cycle 30-50km/week, start with 15km/h
If you cycle 50-100km/h start with 18km/h
If you cycle 100km/h+ start with 20km/h
If you have high stamina from long distance running, swimming, or other endurance sports but you are in the lowest two levels for cycling, increase your average by 3 km/h for the first week, and increase it again by 3km/h for the days after that.
If you plan to take only hotel gear increase your average by 0-2 km/h depending on the hilliness of the terrain. If you plan to take no cargo (i.e. your luggage will be transported for you) increase your average by 1-3 km/h.
If you ride a very heavy (18kg+) bike or a mountain bike with knobby tires decrease your average by 2km/h
If you ride a very light (10kg or less) bike and have road racing tires increase your average by 2km/h
Following this should give you a reasonable estimate of your average speed if what you get falls within the 10km/h to 25 km/h range.
Plan to ride about 4-8 hours per day depending on the amount of sightseeing you want to do. In my experience, 8 hours means all you do is cycle, eat, sleep, and prepare for these three activities (i.e. bike maintenance, food shopping, pitching tents/searching hotels, etc.) 6 hours will give you some time for sightseeing, having a few drinks in town at the end of the day, etc. 4 hours or less will allow all the sightseeing you need.
Plan a rest day (i.e. little or no cycling) every 4th to 7th day. You will need some margin in your planning to cover emergencies, and your body will probably also need to rest a bit more from time to time. Have more rest days in the first weeks, and postpone them if you feel good. If you are not an regular cyclist plan a rest day every 3rd day for the first two weeks.
And now for some general advice for first-timers:
- Get cycling gloves. Your hands will go numb from holding your handlebars otherwise.
- Get cycling shoes or other shoes with a stiff sole, preferably with click-pedals or toe-clips. Your feet will thank you.
- Bike maintenance is important! It is especially important to keep your cogs, chain and derailers clean and you tires at optimal (high) pressure. Anything that adds resistance uselessly lowers your speed. I generally clean my drivetrain every 3rd day, and after days with significant rain.
- Keep drinking and eating.
- look ahead on the map and make sure your supplies are adequate given the distance to the next food stop.
- Keep an extra emergency supply of some salty stuff (I use pringles chips) and some sweet stuff (energy bars) on hand for when you accidentally "hit the wall" from undereating/drinking.
- Don't even think of taking more luggage than just what you need for the day in a backpack. You will regret it.