If you are already a .Mac member then it's easy: let .Mac sync do it for you. If you are not a .Mac member then you can do this:
1) Quit Safari on the old machine (this is to ensure that all bookmarks are synced to disk)
2) Copy the file ~/Library/Safari/Bookmarks.plist to the new machine (ensure Safari is not running on the new machine.
If you want to copy your history as so on copy the appropriate files from the same folder.