3 levels of cache:
1) wp-cache -> stores the output of pages to static html files, and serves them if no changes were made to the backend.
2) php cache (zend, ea, apc) -> stores compiled version of .php files so that they don't have to be parsed every time a script is run.
3) query cache (mysql) -> mysql stores in memory the result sets for the most frequent sql queries (or all queries if it has enough space). If a sql query is run and the result set is cached, the cache is served instead of having to execute the query again and fetch the data from the disk.
I'd say 2) and 3) are easy to implement, and quite beneficial, and i don't see any reason not to implement them. 1) can be somewhat beneficial too, but more particularly if you have few blogs that are visited a lot as opposed to many blogs each receiving few visits. 1) is the one that needs the more care, especcially because the conditions that make a flush of a file from the cache needed are not always easy to see and because any side operation you make needs to adapat to the cache system. By this I mean, for instance if you have batch jobs running against your DB, you need to make them flush the appropriate caches if needed.
I'm not too sure about wpmu cache. I thought it was the same as wp-cache.