It seems to be a tricky process. I found some information on the process online but I couldn't find all the information in one place.
Here is the KB article that most people link to that gives an overview of the process: Connect_the_BlackBerry_Simulator_to_a_BlackBerry_Enterprise_Server
Here is a video making the process look pretty simple: Java Development - Connecting the Simulator to an Enterprise Server - BlackBerry
What isn't mentioned anywhere I've found is that you must allow connections via TCP on port 4101 to your BES server. I don't think it's necessary to forward connections from the outside to your server, but it seems to be necessary when using the BB Simulator.
You get a clue that it's trying to connect on port 4101 if you open the BB Device Manager while it's trying to connect. The BB Device Manager is a program running in the system tray. If you watch the video carefully you'll see him open it one point.