Hi Jacqui,
You'll get as many different recommendations for software as there are Rootschatters - well nearly. Try looking at some of the stuff on
http://www.cyndislist.com/software.htm to gt an ida of what is around. Whatever you choose make sure it can handle gedcom properly - not all packages do - and it should be able to hold details of your sources that provide evidence of what you build. IMHO The Master Genealogist takes a lot of beating since it also has excellent facilities for adding research tasks as you go along.
As to "paperwork" I take a slightly different approach. My research is arranged around the repositories. So I keep a folder of all my visits to, say. Kent Record Office. I have a copy of the "plan" with each research task that I want to undertake and I annotate it with notes about whether I found what I wanted, the state of the documents, distractions etc. It is surprising how useful this can be later on when you are trying to remember whether the entry for "Fred Smith" was really "Fred Smith" or you happened to be reading a difficult document and it could have been something else.
I make a manuscript copy of the records that I research and if I cannot read something then I either get a print out or photocopy or make a manual note as close to the original as possible. I once wrote down a wife's name from the Marriage Register because I could not read it properly. 10 years later I had read more types of handwriting and on revisiting my notes immediately knew what it was!
In the end it won't matter which way you "slice it" the important thing is to have a system that works for you.
Paul