The wp_nav_menu() tag is the big new thing. It replaces wp_list_pages() or whatever else themes have been using to create nav menus. Not much else new on the theme front... there's now a comment_form() tag you can use to print a standardized comment form, but that's the only other thing that comes to mind.

I am trying to keep http://codex.wordpress.org/Version_3.0 updated with the big things, but my focus is elsewhere and the developers mostly haven't touched that page yet.