It's kind of like hardcore paper mache. To get a solid log, you must change the structure of the newspaper. That is from sheets to pulp. Usually there's no shortcuts in paper mache, but you'll learn how to make these logs very quickly using a rubber mallet.
The paper logs burn best when combined with wood. They will create more ash than wood. The hole through the middle will help it to burn and make the drying out process quicker.
Step 1: Prepare the Newspapers
If you have a leaky gutter with a bucket under the drip or collect rainwater in a tank it would be a great idea to use rain water for the logs.
The newspapers in this instructable were soaked for two days. One day is enough. If you want to speed up the softening process put a squirt of cheap detergent in the water.
wingbatwu suggested adding flour to the water which sounds like a really good way of helping everything bind together.
Step 2: It's Hittin' Time
Starting at the top of the newspaper, hit it with the mallet and work your way down until you've done it all. Not too hard or the newspaper will fall apart. Now carefully lift the mashed newspaper from one side and flip it over. Now hit the other side with the rubber mallet.
If you hit the first side too hard you will find it hard to flip the newspaper over. Just turn what you can and piece it back together.
Step 3: Rolling and Squeezing
When you finish, you'll need to make sure that you press the end of the newspaper into the log so that it doesn't unravel.
Step 4: Tidy Up the Ends
Remove the dowel
Step 5: Finished/dirty Hands
Put the logs in the sun to dry. It depends on the weather how long they'll take to dry. The logs I made for this instructable dried in one day. But it was a hot day (30c/86f). If you're making them in cool weather it could take two weeks if there's no sun.
Update, 10th November 2008: I have mentioned in the comments section that once the fire season starts you can get your logs dry within a few days by stacking them on top of the wood heater or in front of an open fire. There is a photo in the comments.
If the weather is lousy, but you haven't yet had any fires you can make use of a well aired spot. If you keep your firewood under cover, it would also be a good place to dry your paper logs. In cool cloudy weather I make a space for the logs to sit for as long as it takes. I put an old screen door on some boxes and use that as a drying rack. Air can get to the logs from underneath. Any area that gets the wind but is protected from the rain will do fine if you can afford to wait a couple of weeks for them to dry.
It's surprising how hard they are when they're dry. If you tap yourself on the head with one, you'll see what I mean.
You really need to make a whole lot of them before winter. Otherwise it will be too cloudy and cold. At the beginning you will probably love making them, so take advantage of this and make as many as you can. After a while your enthusiasm will wear off and it will turn into a chore especially if you're out in the cold and your hands are freezing while you play around with cold wet newspaper.
But anyway... good luck if you decide to make them. Your firewood will last a lot longer.
Step 6: Paper Log Tweaks
» adding coffee grounds to the logs. This could make them give off more heat. The grounds could be sprinkled on top of the paper after it's been mashed on both sides. Then roll the logs up with the coffee grounds inside.
» adding pine needles to the logs to add some crackling. The pine needles could make them burn hotter too.
» improving the appearance of the logs by wrapping in soaked brown paper like from a paper bag.
» adding coffe grounds or related coffee/tea product to the soaking water to give a brown tinge to the logs to make them look nicer.