How to get there
From Moscow take train to Arkhangelsk. When in Arkhangelsk find local aeroport "Vaskovo". There are flights from Vaskovo to Solovki once or twice a week depending on season. Small plane carring no more then 15 people will bring you to the main island in less then an hour. If you don't want to stuck in the aeroport, it's good idea to phone Vaskovo in advance about their schedule.
More reliable, although still without gaurantee rout to Solovki passes through Kem, small Karelian town on the shores of White Sea. From Moscow take train to Murmansk, get off in Kem. Take local bus to ferry terminal. If you are lucky you will find one-two boats ready to go. You will have to negotiate with captain about prices. When I was there last time, the price was depending on number of people, 10 - 20$. It was price for Russians. I can imagine that they charge foreigners "special rates". And yeh if you are not lucky, or weather is stormy, you will stack in Kem for a while.