Update: As of 2016, the train company decided to forbid taking bicycles in trains that do not have storage compartments. In other words, one can not take a bicycle in the train. The trains are mainly without a storage compartment, and those that do have a storage compartment are not regular but may happen to be on a particular line if they can actually move. So have no hope that one of those trains with a storage compartment is going to come. Take a bus.
Taking a train with a bicycle in Macedonia is a tricky thing. The first issue is that there are no special places for bicycles. The second issue is that the trains are very high, so one needs assistance to put the bicycle in the train sometimes. And the third issue is that the train company's policy is not very clear. In general, one can take the bicycle in the train, for a minor fee of about 0,5 EURO, which should be paid to the train conductor. But, understanding that there is no special place for bicycles, train conductors are reluctant to allow bicycles on the train.
So, if you must take the bicycle on the train, do like the locals – be innovative in placing the bicycle for transport in the train. Understand that at the moment there are two main types of trains in Macedonia.
The first type is the trains with coupes, big green cars, do not have any space for bigger luggage. In these trains place the bicycle at the very beginning, or even better at the very end of the train. Place the bicycle in the first car corridor, where the exit door is. Tie and lock the bicycle to the door knobs for moving between cars. Since it is the last car, there is no need of movement for these doors. One can place up to two bicycles on each side. Anything more poses a problem for exiting or entering the train.
The second type of trains, white, blue or even orange on the outside, have some space for big luggage. This space is quite big. However, there is not easy to tie the bicycle to something. And tying is very important so the bicycle does not move while the train is moving. So, improvise. In these trains one can have 10 or so bicycles, especially if willing to load them one over the other.
In any case, do not forget to lock the bicycle somehow.
When taking the train know that Fridays is a crowd for trains going out of Skopje, while Sundays is a crowd for trains going to Skopje. This goes same, and appropriately for beginning of holidays and end of holidays.
Taking in international trains is sometimes a big problem, with the conductors. But since few years the only international train is the one to Belgrade, Serbia since the one going to Thessaloníki, Greece was closed since Greece does not have money to run the service. There are no trains to Albania or Bulgaria, in fact there are no train lines.
Final word about bicycles and trains is: take some beer. If the train conductor may not be happy that you want to take the bicycle in the train, offer him a beer can. It usually works.
Oh, did I mentione that trains in Macedonia are fairly slower than buses, but also slightly cheaper.