Although planning can be done at any time, the first weeks of the year should offer as blank a canvas as you're likely to get.
Planning your garden doesn't have to be an overwhelming operation. Good practice dictates measurements, squared paper, sharpened pencils, soil samples and so on. I think that if all of that seems too much, the back of an envelope and a biro can be perfectly good enough.
Firstly do a rough sketch of the garden as it is. Then, list what you want from the garden. This list from here (requires Adobe) is a great place to start if your not sure what you want.
Then, sketch out as many variations of that space, with those requirements as you can think of. That's where the artistic bit comes in. I could list hundreds of different ideas, styles and methods of design, but it's perhaps better to look for your own inspiration, try gardening magazines, Pinterest, Google, walk around the countryside and visit local gardens. This is a good page for an initial starting point. Each style links to further information about it, with ideas for materials and plants. This guide on the RHS (requires Adobe) gives a more complex but interesting point of view on some of the basics of garden shape planning.
Once the overall design has been achieved you can focus on what plants to work with in the space. It does help to know what type of soil you have, but you can do this easily. Take a quick look at this guide and you'll find out easily. If your worried about the PH (acid, alkali) then look at this guide. Once you know the soil, you need to know your light levels, this couldn't be easier. If it's in shade most of the day (under a tree canopy? North facing?) you'll need shade tolerant plants , if it gets the sun from morning 'till evening you'll need light and heat tolerant plants. This can affect the soil too, you can have dry or damp shaded areas, sunny areas are more often affected by drought too. Once you have that knowledge searching for plants is easy. The Gardeners' world 'plants' section is great for choosing plants and getting inspiration. Another way to find out what will grow in your garden is to wonder around your local area. If it's growing in someone else's garden, or in the wild near you chances are it'll thrive in your ground too.
Once you've chosen what plants you'd like, you need to organise them. Generally you put taller plants at the back and short ones in front. That's about the only rule I can come up with. Group colours how ever you want. Block colours can be very striking, but then so can a riot of colour. I believe its all personal choice. For a bit of direction colour-wise though take a look here. This is a great guide too with good advice, follow the pink links near to bottom for advice on other types of border, each page has good general advice.