Menu sprites in WordPress shouldn’t be any different than any other layout. They’re still generally defined in a class within some kind of nav and the images are being called/moved through the css. The menu code itself in the WP template shouldn’t even be any different.
Even looking at the existing site’s .css, you could probably use Starkers and move the majority of that code directly into it and it should function the same.
Start by copying .css code for the menu into the Starkers .css file, then copy the images into it. And then in your header.php, put in the navigation div in with your <a> tags. It should for the most part function and then you’ll just have to plug in the WP pages once that is done.
Are you planning on using wp_list_pages? The way this thing looks right now, there simply isn’t any room for more menu items. So you could keep the top menu static and link to the correct pages within the <a> tag.
If you do plan on using wp_list_pages, then you most likely need to change the code of the sprites. Right now the hover image is shifting to the right the further toward "contact" you go as one graphic. You’ll need to create 1 style with a fixed width of like 200px and the image will move into it on roll over, and then apply that style to each button. And you’ll need to make the menu smaller so they can add more options dynamically.
But for the sake of the conversion just copy the code as is, at least for now (and I would recommend doing it static if they are happy with the look), and you can change what classes the wp_list_pages uses later.