Florina in northern Greece is a useful staging post from the "Former Yugoslav Republic of Macedonia" (FYROM) into Greece.
While in Greece, to avoid hostility, you could refer to FYROM as "Skopje" or just say the town you have travelled from. This is currently quite a sensitive issue.
Train connections between Thessaloniki and Florina are suspended.
There are frequent buses. Valid information can be found on  (Update: 14/01/2012)
From Bitola it is about 30 km, and takes a little over an hour by taxi. Macedonian taxi drivers require a special permit to operate in Greece, and they might use this fact to quote you up to €40. You should be able to knock them down to €25 or less. If they don't have a permit, they might offer to take you to the border for just a few euros, but you then have to walk between the border posts (800m) and hope to find a Greek taxi. Alternatively, they might take you all the way but pretend that they are a private car once in Greece.