Should new iOS developers use Storyboard and Xibs/Nibs?

Yes! You should definitely use Storyboards to build your applications. One of the neat things about Interface Builder is that it doesn't abstract away the underlying concepts - you are still working with the same types of objects as you would in code (UIViewController, UIView, etc.).

This lets you still learn how UIKit works but experience the benefits of building your UI using a tool.

There is a WWDC presentation from last year that outlines the basics of using Storyboards in your apps:

https://developer.apple.com/videos/wwdc/2011/?id=309

This is quite subjective but I definitively agree. If you want to learn how iOS works definitively start the UI code first. Interface builder is useful to position elements quickly and accurately, but like the article mentions you'll be much more productive after you understand how the views and controllers work together.