First off, auto-rotation can be a little tricky. For example, if you are using a UITabBarController, you will need to subclass it and add the appropriate delegate methods. You should read up on auto-rotation via the Apple docs and Google, before really diving in.
To answer your question specifically though, here is how you would need to declare the UIToolbar such that it will auto-rotate when you have the app set up to do so:
// I keep this definition in a file called constants.h since I use it a lot
#define SCREEN_FRAME [[UIScreen mainScreen] applicationFrame]
UIToolbar *tb = [[[UIToolbar alloc]init]autorelease];
// this frame will position a toolbar at the bottom of the screen
tb.frame = (0,
SCREEN_FRAME.size.height-tb.frame.size.height,
SCREEN_FRAME.size.width,
tb.frame.size.height);
//Setting the auto-resizing mask will make the toolbar resize when the viewController
//it resides in rotates.
tb.autoresizingMask = UIViewAutoresizingFlexibleWidth | UIViewAutoresizingFlexibleHeight;