I would reccommendrecommend starting with Pressflow (if using Drupal 6), Memcache, Varnish, and some form of Content Distribution Network (CDN) such as Akamai. The end result should be as few of those users as possible actually hitting your origin server.
If you have parts of the page that you are not able to cache for non-anonymous users (things that are specific to that user, "Welcome userX" etc.), you can explore options to populate these pieces of the page such as asynchronous callbacks or edge side includes.
If you have a smaller group of internal users (such as a group of editors) that need to be able to view an uncached version of the site, I would recommend exposing an uncached version of your site at a different URL (protected behind a VPN or equivalent if possible).