I use diagramming (a more general term than mind-mapping) techniques extensively and my experience reminds me the first thing to consider is what you are going to do:

• If you want to generate ideas (that is brainstorm by yourself) mind-mapping is a good technique. A good manual on mind-mapping can be found here: http://www.mind-mapping.co.uk. So how to do it - by hand or on paper? On paper you wan have virtually as much space as you like, it definitely feels more natural and you are not restricted in drawing style by software. On the computer the benefit is faster intput (especially if you are a touch typist) and fast input is crucial when so many ideas and associations rush into your head.
  

Even though mind-mapping is touted to be the ultimate tool just for this purpose I still do not adhere completely to it. On the sheet of paper I often do diagrams following different direction than that from the centre outwards, make various inter-connections, etc. Of course there is software for such, "free", diagramming - e.g. MS Visio.

• If you are going to present some information to other people I would advise you to use hierarchical diagramming - that is, all graphics having a clear, linear direction. Also do not make the diagram excessively colourful - actually do not use colour unless there is something very important to underscore. This seems contrary to the concept of mind-mapping but do not forget that creating ideas is one thing and reading ideas another.
  

• If you need to systemize knowledge from several sources into one single scheme or make a graphical outline of a book then mindmapping software is the answer. I would wholeheartedly recommend you www.mindmapper.com - versatile, flexible, oriented at the diagramming functionality rather than the decorative effects.