The letter should have told you some of the things you will have to do. As well, you can phone the Immigration Appeal Division that is handling your appeal and ask for advice - for me, they were more helpful than the CIC call line.
You have to show that the reasons the visa officer gave for rejecting the application are not true. So look at the refusal letter to see what the problems were; also order your GCMS notes to see what the visa officer wrote there. Together you should be able to see what the problems were.
Then gather proof that shows your side. At an appeal hearing for immigration, they allow new evidence, so get evidence from the time of the refusal up til the appeal. You can also get more evidence from the length of your relationship, but keep in mind that the judge might wonder why you did not present that evidence in your application.
Many people who are doing a full appeal get a lawyer.
