Train, car, bus connections are with the local town on the Polish side, Terespol.
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.
If you are already in Terespol and need to cross over to Brest, you can walk over to the border crossing and "hitchhike" across with one of the cars that is already towards front of the line. They might be happy to take you across as they can "assign" some goods as belonging to you for the purposes of customs. Just go along with the arrangement. Alternatively, they might ask for a modest payment of $5USD or so.
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 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.
Buses will not run after 11.30 so you would need a taxi.
Belavezhskaya Pushcha  is an ancient woodland straddling the border between Belarus and Poland, located 70 km (43 mi) north from Brest. It is one of the last and largest remaining parts of the immense primeval forest which once spread across the European Plain. It is a UNSECO World Heritage Site.