Train, car, bus connections are with the local town on the Polish side, Terespol.
Atlant Soyuz (Russian Airline) recently started direct service from Moscow. Tickets are ~$175 round-trip. It is 2hr40min flight. Here is the website of the airline: http://www.atlant-soyuz.ru/en/?switch_site=1
You can also fly to Minsk or Warsaw and take the train (see Trains section for details)
See Belarus. Get out: the customs control in the Brest train station is not very obvious. About an hour or so before the train leaves, you'll see people waiting at a railing next to some glass walls which look they open up to some rather bland and unused empty room. They look a bit like people waiting for arrivals at an airport, except that it's not obvious who they are waiting for. In fact, they are waiting for the customs office to open. If you're trying to leave Belarus, then join the queue a good deal of time before your train leaves. If you arrive only ten minutes before the train leaves, chances are good that the train will leave without you, not because the queue is too long, but just because the rules are strict.
The train from Warsaw runs 3-4 times a day and costs 150 zloty (~$60USD). Alternatively, you can take the train from Warsaw to Terespol (on the other side of the border from Brest) for 40-60 zloty ($15-20USD) and then take a commuter train from Terespol to Brest (runs twice a day) for ~2USD. You can check the schedule for both types of train on Polish Railways website 
The train to/from Minsk runs ~20 times per day and costs ~$5-20USD. You can check the schedule on the Belarussian Railways website (note: only in Russian), which has a graphical map to select cities. 
See Belarus. There are six control lines of various sorts at the crossing. Allow something like 2 hours to get through them all.
Confusing transport system. Even locals can have trouble getting around on a bus.
Transport within Brest city is very regular, with many different bus route through the city, and also regular trolley-buses through the city. Taxis are also easy to order and "mashrutkas" (Private minivan taxis that follow bus routes) also operate throughout the city. The main attractions are all within walking distance.
There is a museum, where you can learn about fight between attacking Germans and defending Soviets. There is also small part about Polish defenders of this place, who were attacked earlier by Germans and Soviets. The history of Brest Fortress is complicated, as you can see, and worth learning.
There are many shops and boutiques on Sovetskaya street, which sell all kinds of products from fishing gear to real designer wear. Smaller shops are dotted around the town centre and there is a big "TSUM"- Central Department Store on Moskovskaya street.
Hotel Belarus 6, Shevchenko blvd. Central location, several blocks away from river Muhovetz. Rooms can run anywhere between $30-70/night for foreign citizens. Belorussian citizens still enjoy lower rates.
Belarus has a low rate of crime, and mostly the atmosphere is very friendly even on big celebrations (when everyone is drunk) :)
Try not to wander off too far at night.
Never use taxi travel at night time. Busses will not run after 11.30 so you would need a taxi.