Generally planning the trip for June, July or August is best. Tourist season starts in late May, though there can sometimes be snow in some places even then (though the roads are generally clear of snow). Early September is another possibility and fall colors are already starting to show, but by mid September many tourist facilities are already starting to slow down.

Best with a rental car is to book as soon as you can. I generally plan my Alaska trips more than a year in advance. That way I can book a rental car 10-11 months in advance. Waiting longer than that and the rental car cost can easily double or triple.