I just completed an upgrade (of this site) from Drupal 5.x to the latest version of 6, and I'm happy to report that it's pretty seamless, IF, you have shell access on your machine. I'm using lighttpd, but you shouldn't experience any issues doing this upgrade with Apache. The key here is to leave your old install in place and create a new database and directory in which you'll use Drupal 6. Keep in mind I'm running a largely stock release of Drupal. If you are using third-party modules for Drupal 5.x modules, I would not recommend updating -- however, with this method you can always revert back to your old install, so the only risk is a little downtime while you're working. Step by step after the jump.

Here's what I did:

1. Create a new dir in your web root. For this example, let's pretend it's "/var/www/root".
2. Unpack the latest 5.x version to "/var/www/root". The easy way to do this is wget the latest 5.x release to your home directory ("home/my_user_name/drupal-5.x"), then "cd /var/www/root", and "tar -xvzf /home/my_user_name/drupal-5.x".
3. Set up a link to the extracted directory with "ln -s drupal-5.x drupal" in "/var/www/root"
4. (Optional) Create a new MySQL user.
5. Copy your current Drupal 5.x database to a NEW database. To make this simple, you can use PHPadmin, and select "operations", "copy data and structure" to a new database. Let's pretend this is "drupal_my_site". You can name it whatever you want.
6. Change your httpd configuration to point the root of "www.yoursite.com" to the new "/var/www/root/drupal" dir we just made, and restart your webserver so the changes take effect. In my case, I did a "/etc/init.d/lighttpd restart", but you'll probably be doing a "/etc/init.d/httpd restart" or "/etc/init.d/apache restart".
7. Load "http://www.yoursite.com/update.php". Drupal should complain about not having access to the default/settings.php. Change the permissions, reload, and then Drupal will ask you for a db name and user, enter in "drupal_my_site", and your MySQL username/pass (the new one if you made one).
8. Drupal will ask you if you want to upgrade. Continue through the upgrade process.
9. After completing this process successfully, wget Drupal 6.x to your home directory. Again, "cd /var/www/root", and "tar -xvzf /home/my_user_name/drupal-6.x". This will extract the Drupal 6 files to a drupal-6.x subdir. Delete the drupal link you've made with "rm drupal" in the "/var/www/root" directory.
10. Relink the "drupal" directory to "drupal-6.x" with "ln -s drupal-6.x drupal" in your "/var/www/root" directory.
11. Take a second to check your php.ini settings! You *may* need to increase your max_input_time and memory_limit settings. You can search for these settings within your php.ini file. If you don't know where your php.ini is, you can create a file in your web root called info.php, and add the single line "phpinfo()" in it. When you open info.php, it will print out a bunch of information about your php installation, including the location of the php.ini file you are using. Usually you will have to become root or sudo to make any changes to these files. PHP usually installs with a memory_limit of 8M. In my experience, this will not install Drupal 6 from scratch, much less do an upgrade. I found that my settings of memory_limit=16M and max_input_time=30 did not allow my upgrade to complete. I changed these settings to memory_limit=64M (the most I have on this little VPS!) and max_input_time=360 and everything completed fine. Remember, after you change these settings you will need to restart your web server! Again, in my case, I did a "/etc/init.d/lighttpd restart", but you'll probably be doing a "/etc/init.d/httpd restart" or "/etc/init.d/apache restart".
12. Now, visit "http://www.your_site.com/update.php". We don't need to make any changes to your web config, because it's still looking for the 'drupal' subdir, which we repointed in step 10. You may need to again enter your database username and password -- I already had this step completed, so I got a page with Drupal complaining about not permitting an update unless the $update_free_access variable was set to TRUE in the default/settings.php file. If you've logged into drupal as an admin before opening update.php you should not get this message. If you do, go ahead and change this to TRUE (you should remember to set it back to FALSE afterwards -- Drupal WILL remind you of this, however).
13. Cross your fingers and hit the update button. Hopefully everything will go as planned.
14. You're done! Reset the perms on your sites/default/settings.php file/directory, and enjoy Drupal 6. Again, if you find that the update does not complete, the most likely reason is that Drupal has ran out of memory (or input time) while attempting to update. If it freezes in the middle of the update, drop the NEW database we made (double-checking to make sure it really IS the new database), and start the process over, but this time set your memory_limit higher before attempting the update process.

If your update process fails, you can always go back to your old install simply by editing your web server config to direct back to where your old Drupal directory lives, so this is a no-risk proposition if you work carefully. I would HIGHLY recommend backing up your database regardless (using mysqldump) before trying this procedure in case of a slipped finger or some other disastrous result. Drupal 6.x is EXCELLENT, particularly on the developer side (a lot of sensible changes have been made to the menu/form/templating systems), and I would recommend that if it is possible for you to upgrade, you do so.

Good luck!