Terracotta bricks are actually pretty rare.
These can be purchased of amazingly high prices from specialty tile shops and the like. There are however quite a few terracotta products sold in National Chain and Mom N Pop pet stores that work perfectly. (I am searching for a picture of these online, but have yet to find one.)
Red Brick is fast falling out of favor in the construction realm due to costs and labor, however there are quite a few sources available. Construction/ demolition sites are choice. In the past I have merely asked for a few stray bricks from an employee/foreman at the site and invariably was offered all I could take. To purchase them, look for "red brick pavers".
Many DIY stores carry them in stock, many others can get them for you. Even Googling the term brings up plenty of places to get them. (Bet the shipping is costly online though) I buy them from the garden center at Home Depot. The downside to pavers is they do not always have the holes through them. The good news is a lot of architectural salvage places have those old style "holy" red bricks.
Local brick yards most certainly carry them, or can get them. I am a fan of Higgins Brick and their products. They make brand-new bricks of all sorts, including some that are amazingly weathered looking. The local brickyard here laughs at me a lot, but they still sell me bricks.
A third option is to contact the local Bricklayer's/ Mason's Union (not Freemasons- the actual construction guys...). A lot of those guys can help you out or may even have bricks you can get.