Part, and then colour. Colour works for smaller amounts of brick, but as your collection grows larger almost everyone has the need to resort by brick type - If you start with it, you avoid the work of resorting!
It's important to only sort the pieces you're really interested in having sorting: It's an entirely futile exercise to attempt to sort every piece you have into it's own space.
I use various containers:
LEGO Tubs for most basic bricks, slopes, etc.
-
Bead Trays like this for small pieces like 1x1 bits, minifig accessories, etc. I have 70+ of these trays. I have labels for many of them...if you're interested in the my file for the labels, just ask!
-
Drawers; This certain set contains most of my plates 2x6 or smaller, and a few other pieces like arches.
-Ziplock bags for each colour of larger plate.
-Pick-A-Brick cups for "overflow" amounts of pieces.
There's many other bins and containers I use - Any collection is in a constant state of sorting, as you get more parts you have to change around bins, get bigger ones, etc.
I admit, I sort in a much more detailed way than many people: I just generally find it better to sort by brick first, and then by colour underneath that if I feel it's convenient.
-John.