External HDD is the best choice.
If you do it on DVDs, make sure to burn the music folders directly from
user>music>iTunes>iTunes Music (artist and album folders are here, as well as podcasts/movies)
I would do something like: artists 0 - E on one DVD, F-K on another DVD..etc..
Once all the folders themselves are burned to DVD, copy all contents of:
user>music>iTunes (this contains the "iTunes Music" folder, Assuming you saved the contents of it, delete this folder.) Once the folder is deleted, or at least skipped, you should easily fit the rest of the files on CD or DVD.
These files include:
Album artwork (folder)
iTunes Library
iTunes Music (folder. Save this seperately as it is the largest.)
iTunes Library Extras.itdb
iTunes Library Genius.itdb
iTunes Music Library.xml
Previous iTunes Libraries (not really important, at least not to me)
Temp File.tmp (no clue what that even is.)
When you get the new mac, Open the Music folder, and drop everything back the way it was. If there is already an iTunes folder present, delete it, and replace it with the saved library.
Open iTunes for the first time, skip through the prompts, and you'll be brought to the library, already fully operational. No re-adding, sorting, or anything. Playlists, songs, everything should remain intact.