What sort of store does one go to to buy stair parts?
The term you're looking for is millwork, which is a catch-all term for finished wood products, and includes the stair parts that you mentioned. From Wikipedia:


  Millwork building materials are historically any woodmill-produced building construction interior-finish or decorative components. Profiled and patterned millwork building components can usually be installed with minimal alteration. Today, millwork encompasses items that are made using alternatives to wood, such as synthetics, plastics, and wood-adhesive composites.


A lot of them will have the word "millwork" in their company names, and if not, should at least show up in a web search. 

If they don't carry the exact pieces that you want, you may find some will be willing to mill items to your specification; this can be useful if you're trying to match hard-to-find trim.