Flash. You can get a vector map from Istockphoto.com and then have all the rollovers be different colors.

Remember: you also have links to each state for the bots, although it is very helpful for a minority of users as well.

I tried it with image maps and it is really bloated code and not a very nice effect.

I would go for Flash.. But there is a similar function in Macromedia Fireworks where you can get rollover effects, and I think a number of other similar programs.