Both. 
Although you can stick a tiny breadboard on a protoshield, they come in most handy when you want to solder down a working prototype sturdy enough to carry around. Or if your circuit is simple enough and you don't mind doing some re-soldering while you tinker with it!
On the gripping hand, when you cross a component count of half-a-dozen discretes or one 14-pin dip, you'll really want the space of a full breadboard to play around with.
There are even a couple of Arduino-clones, such as Lady Ada's "Boardino," specifically designed to clip into a standard breadboard.
As an aside, there's a shift in philosophy that comes when you really start leveraging the power of a built-in micro-processor. Many tasks you might have attacked with a handful of components -- say, switch debouncing -- turn out to be just as easy to handle in software with an extra line or two of code. Even little tricks like pulling down switches to ground or ballasting resistors can be done, essentially, internally to the Arduino. So the component count for your breadboards may not always be what you expect.