The only bus i found is Simeonidis tours, N⁰ 14, 26th October St., leaving every day exept sunday about 5.30 pm, € 20 (€ 25 return) taking about 5 hours, did have a stop in Negotino ans Veles.
Buses to Romania you can also find in 26th October St.
There where 2 overnight and 1 daytime buses (9 am, 8 pm and 9 pm) from Thessaloniki KTEL Bus Terminal Makedonia, Giannitson st 194 to Tirana (in april 2011, maybe more in the summer): one of them at 8 bpm, arround 1 am Korce, 5 am Durres, 6am Tirana.
Buses to Albania seem to leave now (march 2012) only from Giannitson street opposit the railway station from the bus offices, Albania Express, Giannitson str. 75 and Alba Trans around the corner there, € 32.
From Giannitson str. 63 to Sofia € 28 at midnight and maybe also at 14.30 (and other Bulgarian destinations).
If you don't want ot mess in small mountainy roads, go to Patra via Athens.
All the way until Korinthos 580 km is a motorway (autostrada or autobahn) the rest is highway.
The whole distance is 700 km and tooks you almost 7-8 hours.
Otherwise the distance is 500km and 7 hours but mountainy roads and easy to loose your direction NOT SUGGESTED
KTEL, the national bus operator provides good connection to and from Thessaloniki. Check their we page for details.
I found KTEL a professional firm, rendering good services at fair prices. Most buses are air-conditioned and you can communicate with the staff in English.
Intercity buses are a common way of travelling around Greece, the standard is medium and little english is spoken, but a new terminal has just brought all such regional services together. The KTEL station, as we call it, is a bit out of town, direction towards Athens, easiest way to get there is by taxi, should cost 3-5 euro from town.
Three city lines service the bus station, bus no 31drives via Egnatia street, no 78 goes all the way to the airport and crosses the center via Mitropoleos str. near the sea...