Many people who already  have a canoe do not therefore have the luxury of choosing the "ideal" design.

The best type of canoe (ie size in terms of length, beam and volume) will depend on whether you wish to sail with just yourself in the canoe or with others and/or camping gear.

For most purposes you would not go far wrong with

	a "general purpose" canoe
	length - 14 to 17 feet (4.5 to 5.5 metres)
	beam - 34 to 38 inches (about 1 metre)
	depth - 10 to 12 inches (about 0.3 metre)

Luckily these are the type of canoes which are most common and which many people will already own.

For purely downwind sailing the canoe hardly needs any adaptation at all.  Many people are quite satisfied with holding out some kind of sheet of polythene or tarp to catch the breeze and get a free ride.
 Using paddles or punting poles to hold the sheet up can be a useful improvement. Here's a basic version with pockets sewn into the top corners:

Here's a ready made version from Endless River.  
A very simple square-rigged sail can be made from the two halves of a punting pole, a tarp, some lengths of cord and a simple socket on the bottom of the canoe with a lashing for the half-pole "mast" to a thwart/cross-member. 
This example uses a strong and substantial mast step:

Some people have tried to use a clamp onto a thwart to avoid having to fix anything to the floor of the canoe but this arrangement will not be strong enough in any kind of useful breeze and may break the thwart:
 
This type of system is therefore not recommended!

There are versions that use a poling pole but allow the sail to be set in line with the length of the canoe but these still only provide downwind sailing, but perhaps at a slight angle across the wind:

(This canoe is trimmed rather poorly, being very stern down!)

These methods so far have the advantage of making use of the gear that many canoeists carry anyway.  The disadvantage is that the canoe will not be capable of being sailed across the wind at anywhere near right angles, let alone being tacked against the wind.  For this you need a "proper" sail and some means of reducing the canoe's tendency to slip sideways across the water whenever you try to steer in any direction other than downwind.

For most people this will be a leeboard; at its simplest a plank sticking down into the water parallel to the side of the canoe and held in place by a bracket or lashing (or even a couple of "G-clamps" to start with!  Watch out for shallow water though!)

The "proper" sail will need to held up by a mast which must be "stepped" fairly strongly.  Stays to help hold up a mast (like guy-lines for a tent) are not really practical on a canoe as it is so narrow it offers such a poor supporting angle.

The minimum bits of kit you will need to add on to your canoe for effective upwind sailing are therefore a mast-step and a leeboard mounting:

If you wish to retain the versatility of the canoe for paddling as well as sailing purposes some care is needed in the design, construction, positioning  and fitting of these minimal add-on items necessary for canoe-sailing. 

Some boat constructions and/or materials lend themselves easily to the fitting of the mast step and leeboard bracket as they are inherently stiff enough without having to add any bracing structure.  However with some thought, care and ingenuity even the flimsier models of single-skinned, internally-framed, plastic canoes (such as Coleman) can be sailed successfully.

More pictures of canoe fittings etc

Link to a specialist UK supplier of rig-making materials, complete rigs for self fitting and fully rigged canoes

Link to an American web page showing a partly improvised canoe sailing rig.