i've been to big bend several times paddling and hiking and researched biking a few years back--Terlingua has some bike shops and maps to mountain biking. you have to road bike a long way to get anywhere in the park. google or call them.
it's a great place, but i'm not sure biking is the best way to enjoy it.
I went for spring break 2 years ago and regretted I did not bring my bike. It is solitude out there, the park has tons of road to ride on with very little traffic. Be sure when you get there to attempt to get a back country pass for the mountains, they are limited on camp sites.