Craig:
I do agree with John, April and May is pushing the early end of the season for a ride such as what you have planned.
What makes further analysis difficult (I'm going to try it, bear with me) is that you will be crossing no less than 7 totally different climatic zones between Halifax and Anchorage. Heck, you are hitting every climatic zone possible in meteorology with the single exception of desert, and if you really want to hit that one, just take a slight detour to the sand dunes in Northern Alberta.
If you begin in Halifax in mid-April, you shouldn't have too many problems while you are in the Atlantic region of Canada (Nova Scotia and New Brunswick). You might get nailed by a snowstorm, but the odds are against it. However, it is not going to be comfortably warm - evening temperatures will be near freezing - and daytime temperatures of +5 to +10 C, with rain, are common that time of year.
Once you start moving inland from the Atlantic Coast and the Gulf of St. Lawrence (in other words, once you are west of Quebec City), snow is not uncommon during late April, and cold temperatures - daily highs of +10C or less - are the norm. Once you get to Montreal, you face a fork in the road - go north-west up the Ottawa River, following the trans-Canada highway, or continue south-west toward Toronto?
If you go north-west along the trans-Canada, you are going to be encountering cold temperatures and a very real possibility of snow-packed roads (not just a one-day dusting of snow) as you move northward. You will be away from all bodies of water that temper weather. I grew up around North Bay, and well remember making snow forts in April, and I remember frozen ponds on May mornings. Folks who live there don't take their snow tires off their car until the Queen's Birthday in May.
If you go south-west to Toronto, no big problems, you won't freeze in late april April. In fact, from Montreal down toward Toronto, you will encounter milder temperatures than what you left behind.
However, eventually you will want to proceed westward, and from Toronto, the only way to do that is to head straight north to go around the top of the Great Lakes. I can promise you that once you reach Sault Ste. Marie, all bets are off prior to May 15th. You might have dry sunny days with temperatures of +5 to +10, you might get a cold snap with temperatures down to daytime highs of -10 C along with a large (and persistent) dump of snow.
Going around the top of the Great Lakes, most especially around the top of Lake Superior, during the latter part of April or first half of May is a crap-shoot.
Once you hit the eastern border of Manitoba (let's assume it is May 15 now) you are into a different climatic zone altogether. Canadian farmers from the Manitoba border west can generally count on a 95 day frost-free growing period - that starts about mid-May and ends in late August. The good news is that the weather will be drier, and you will have more sunshine as you leave the Great Lakes behind you, the bad news is that it still won't be reliably warm, you could have highs of +10 to +15 and lows very close to freezing.
You'll have to move north and west toward Anchorage, which means that the average daily temperature will remain unchanged for you from what you encountered when you entered Manitoba until at least when you leave Northern Alberta to go into BC. It might get colder as you go northwest, it certainly won't get any warmer.
The land rises once you get into BC, again, the second half of May is a bit iffy up there. By June 1, it's OK - plus, you have lots and lots of light (20 hour days).
All in all, I think you are about 15 days early.. If you left Halifax on May 1, life would be rosy and you would experience the best that Canada has to offer. If you left Halifax on April 15th, you might just freeze your ass off for the next 30 to 45 days.
So, I recommend you try and push your departure date back to May 1.
I've done a few cross-Canada runs in the past, in June, and even in June it can be chilly north of the Great Lakes.
Michael