Having spent a number of hours this past week figuring out how to add a new line item to the checkout process, I've decided to put a tutorial. I have three reasons behind this:
1) To save others from having to go through the same process of having to figure it all out like I did
2) To save the process in a central area so that I can refer back to it myself!
3) To get feedback on parts of the process I've done incorrectly, or to add parts that I may have missed
The tutorial can be found here: Ubercart: Creating Line Items Tutorial.