Located in the bend of the Rio Grande, Big Bend National Park is located in west Texas and encompasses over 880,000 acres of land. One of the more remote parks in the lower 48, the area covers a wide arrange of environments - from desert to mountain to river. Much of the rock in the park is not congenial to climbing as much of consists of unstable igneous rock. However, there is climbing to be found and, in many cases, you may find that you and your party are the only souls for miles around.
Be aware that, if you do find yourself climbing in the park that the environment is harsh. The region is extremely arid and even on what seems to be a cooler winter day, the rock on exposed faces (as most are) is hot to the touch.
As this is a remote park, you will first have to pick a jumping off point.
Ask at the BBNP park office for the climbing booklet entitled 'A Climber's Guide To Big Bend National Park', written by a park ranger and covering several climbing area with pictures and some topos. A ranger pulled a copy hidden away in a cabinet drawer when I asked for climbing info several years ago. There aren't too many climbs in the guide, but enough to keep you busy for a few days. All trad, some mountaineering. It lists 17 trad climbs at Grapevine Hills, 5.6 to 5.10.
Whoops. This has slowly evaded my attention. I have intended to expand what I put up there so I will apologize now for the late response, Sara. When I was last there (about 10 years ago now), we climbed over near Indian Head. We didn't have a guide and I put this up hoping that someone would be able to populate using there own experience. At Indian Head, there were actually a fair amount of sport climbs as well as bouldering and I couldn't discount trad (although I didn't look closely). The rock was mildly creepy (i.e. friable in appearance) but seemed solid. Though it was cool in the morning, the rock was hotter than hell by midday even though it was winter (this is because it was south facing). I will try to put up some pics that we took then.
While there are several small areas in the park, the main climbing area is at Indian Head Mountain with most of the climbing outside the park boundary on private land. Routes are spread out and sometimes hard to see. The parking area at the end of the road affords a nice view of several classics most obviously Thor's Flake, a large exfoliated flake. Many of the nearby boulders have problems and sport anchors for TR's. The climbing guide mentioned in a previous comment is still available at the Panther Junction visitor center and it is perfectly acceptable to request a copy.