Where exactly are my element type custom statuses stored and used?
For starters I'd classify statuses in two groups - static statuses and dynamic statuses: 


Static statuses are set explicitly
Dynamic statuses change according to other circumstances (other attribute values, lunar phases, whatever)


For static statuses you'd go with the approach Lindsey outlined and just define a column for that where to store everything, however, things get more interesting when you start tackling dynamic statuses.

For that, you should look at the Entry element type.

/app/elementtypes/EntryElementType.php
/app/models/EntryModel.php


You'll want to look at the EntryElementType::getElementQueryStatusCondition() method - adding this method to your Element type will allow you to use "status" criteria when searching for elements. As a nice side-effect, this will also make the status filter in the Element index work nicely.

Another method worth looking at is the EntryModel::getStatus() method - implementing this method ensures that your Element type actually returns the correct dynamic status when asked for it.