1. Open the Scripts dialog and run "Export Slices" script.
In the "Save for We" dialog that opens, you can define optimization settings for each slice.
2. For example, click the slice with the main photo, choose JPEG format, and set quality to 70%.
3. Select the preview slices (holding [Shift] key) and set 60% quality.
4. For the text navigation bar slices, try GIF format with 32 or 64 colors.
5. Now choose the optimization settings for auto (gray) slices. Note that all the auto-slices are linked to each other. This means that by editing any of those you modify all the other auto-slices as well.
6. Click "Save" and -- in the next dialog -- choose the target folder for the slices.
7. There appears one more folder selection dialog. Choose the same folder as in p. 6.
That's about all. Now the HTML file must be in the specified folder, and the slices -- in the "images" subfolder.
NB. For more detail on slicing read the full Photoshop documentation.