How to setup a Multilingual site using A LOT of taxonomy terms and CCK content taxonomy?
Check this for taxonomy translation:
http://drupal.org/node/335205

The approach for menu translation depends on your menu and site structure. It is a bit painful but I would recommend using the menu translation interface. Managing multiple menus may work fine if you are planning 2-3 languages max but as you add more languages it will get out of control.