Marcus Zarra posted a great solution to this on the SDK mailing list:
UIViewController *controller = [[[MyViewController alloc] init] autorelease];
UIViewAnimationTransition trans = UIViewAnimationTransitionCurlUp;
[UIView beginAnimations: nil context: nil];
[UIView setAnimationTransition: trans forView: [self window] cache: YES];
[navController presentModalViewController: controller animated: NO];
[UIView commitAnimations];
There are transitions for flipping and page-curling. If you are set on fading, can try adjusting your new view's alpha:
UIViewController *controller = [[[MyViewController alloc] init] autorelease];
controller.view.alpha = 0.0;
[navController presentModalViewController: controller animated: NO];
[UIView beginAnimations: nil context: nil];
controller.view.alpha = 1.0;
[UIView commitAnimations];
However, what you probably want is a crossfade, or at least a fade-over. When the UINavigationController switches to a new view, it removes the old one. For this effect, you're probably better off just adding a new view to your existing UIViewController and fading its alpha in over time.