You should follow the instructions from MySQL carefully. It will be a lot of work. There are significant structural changes to MySQL between 3.x and 4.0, 4.0 and 4.1, 4.1 and 5.0, and 5.0 and 5.1. Remember that 5.1 is beta at the moment anyway, so I wouldn't use that in production. Any jump straight from 3.x to 5.1 is probably a bad idea, though it is certainly testable
I made the jump to 5 from 4 and it was difficult. It took a bit of work. Besides structural changes to the database, the client libraries change and this will break PHP, so you need to upgrade that too. If you're running Perl, you'll want to examine the implication for it as well. It might be a better idea to do incremental changes, from say 3.x to 4.0, then to 4.1 and then 5.0.
Good luck.
