In Canada (and I believe also in the USA) no licence is required to operate a laser transmitter. Keep in mind though, that for amateur radio purposes (i.e. for the QSO to "count"), the contact has to be made between two licensed amateur stations.

In Canada several government agencies have regulations concerning the operation of lasers.
From the safety standpoint: be careful about pointing lasers at people and animals: even though we only use a few mW of power it is very concentrated and can cause severe eye damage especially at close (<100m) range. DO NOT LOOK INTO THE LASER BEAM AT CLOSE RANGE! You can use a sheet of paper, or even your palm to "follow" your beam in the back yard when playing with aiming, etc.
You must also take care not to inadvertently interfere with vehicular traffic (cars, boats, airplanes). Handle your laser like you would a gun: always know where your beam could end up!

There are several webpages dedicated to amateur laser communications. They make for interesting reading and can be easily located by doing a Google search.
The is also a very interesting mailing list sponsored by QTH.NET .

To quickly get into lasers I found the easiest way was to get a couple of Ramsey Kits . Their LBC6K kit is easy to build and quite inexpensive.

Once you have them built all you need is two 9V batteries for the TX and RX, and a pair of headphones or speakers to hear things.

To actually communicate over a few kilometres you have to aim your laser. First you should make sure that your beam is as focused as possible. The Ramsey laser actually has a collimator lense ("focus") built in. If you look directly at the front of the laserpen you'll see two little notches around the rim. You can rotate the lens by inserting a small tool (e.g. very small needlenose plyers) into them. Point your laser at a smooth surface a few feet away and rotate the lens to make the beam as small as possible.

Now you have to mount your transmitter. The best thing to use is a camera tripod. Try to get one where you can have the laser at a decent height. You are going to spend a lot of time hunched over it! Make sure your mount is sturdy. You don't want it to wiggle to the slightest touch. 1 degree movement over a mile results almost a hundred feet displacement at the other end. You should also put a small rifle scope next to laser transmitter to help with aiming.
Then you have to figure out a way to be able to move your beam in VERY small increments. Mounting the transmitter to a couple of pieces of plywood hinged at one end will take care of the AZ/EL rotation. Use a threaded rod at the other end with a couple of bolts and you can raise and lower the platform quite accurately.

Here is a picture of VE7DDR's mount. This tripod has the built in mechanism for the azimouth rotation. On my setup I taped the laser to a 12X2" strip of wood that is attached with a wood screw at the front and I just move the end of the strip by hand.

You can use car headlights or a decent sized flashlight to get an idea where the other station is. We were able to see a 12V lantern type flashlight at 10km quite easily.
Once you know approximately where to aim comes the rifle scope into play. My setup usually gets jarred in transport, so after I set up I have to calibrate it. I aim at a solid surface a few hundred feet away and centre the beam in the crosshairs. In the dark you should be able to see your "spot" with the naked eye a couple of hundred feet away on a tree or a rock. If you want to be real precise you should take into consideration the misalignment of your scope and your laser (i.e. their line of sight is offset by an inch or two: if your scope is two inches to the left of your laser, your crosshairs should be two inches to the left of your spot). I found this inaccuracy to be the least of my problems.

Now you adjust your tripod legs as near as you can and move the laser until the other station is in your crosshairs in the scope. Hopefully he'll let out a "WOW" on the 2m liason frequency, but it's quite unlikely. He'll grab the binoculars and start looking for a tiny red dot. You keep moving left-right, up-down in an organized fashion until he sees you.
This is the part where teamwork comes into play. You have to figure out a way to effectively communicate on the liason frequency. You must also assume that the other guy is actually trying, not just picking his nose as this process can be quite frustrating. If you are close with your aiming he should see a bright flash or two as you sweep by him. He may accuse you of "moving too fast" but you should be patient with him.
Once you get close, it's a good idea to use a scale of 1-10 to indicate brightness. As soon as the beam is decent brightness comes the next trick. The receiving station should move around with HT in hand and actually find the maximum brightness. It is important to set up in a spot where there is room to roam (beach, parking lot, etc.) for this. Often it is easier to move the receiver into beam than to move the beam to the receiver. If you are quite a ways off he can also tell you that you are to his left or right (or up/down) and you can make more adjustments.
Once you are aimed do not turn off the laser to save battery power. The slighest touch will throw you way off! I probably got a good 10 hours TX time out of a battery.
How do you know if you are in the beam? Don't worry about that, you will know. Even over several miles it will be brighter than you thought it would be!
Of course the other station has to repeat the above procedure to get his beam on you.

For the receiver setup we use a simple Fresnel lense (plastic "book magnifier",$2.00 at the local Dollar Store). You can find the focus point quite easily in a dark basement and the receive diode can be gently bent up and down to put it in the focal point.
Our longest QSO was over 7km and I could easily see the "red dot" on my palm behind the lense.
The receiver appears to be fairly sensitive, even when the "red dot" is not visible the signals were quite strong. We just used the little built in microphone on the laser transmitter, so far there was no need for CW.
This picture shows VE7DDR's setup, mine is very similar.