First, draught-proofing
Close the gaps around windows, doors, between floorboards, gaps where pipes go into walls and floors. It's a cheap and relatively easy way to stop a lot of heat escaping, and to cut down on the convection currents that will take a lot of heat from the bottom to the top of the house.
Curtains around the stairwell?
Can you put a curtain around the bottom of the stairwell, and one just past the top of it? They should be floor-to-ceiling, and wall-to-wall. That will help reduce vertical convection. Do take into account safety; and, as with any work, check with Building Regulations.
Glazing
As you've currently got single glazing, then double- or triple-glazing offer lots of energy savings, as well as making it much quieter, and more secure. Not all double-glazing is equal: look for very low U-values, and try to avoid the national branded installers advertised on TV, which tend to be complete sharks. If the building is listed or in a conservation area, you may need to consider secondary glazing, which can offer the same improvements to air-tightness, quietness and physical security, but typically with higher U-values (i.e. higher heat loss).
Thermal imaging camera
I agree with Darren Cook that going round with a thermal imaging camera would be a great way to diagnose the biggest problems, and that in the absence of that, the roof is prime suspect (once you've got rid of the worst draughts). Do it in winter. You may be able to borrow a thermal imaging camera from your local library (some do this), or see if your council offers the service through other routes. If you've got a local college that teaches architecture or building-energy, see if they want to use your house as a research project: ideally, they'd come round in winter and do a blower-door test (to measure air-tightness) and go round with the thermal camera during decompression: that will suck in air from the outside through all cracks, and you'll see blue plumes on the camera where the leaks are. Run around putting post-it notes on the leaky bits, to go back and fix later.
Look for mould or condensation
If you see mould, or an area that repeatedly gets condensation on it (most noticeable after cooking or bathing) that will become mouldy, start there. The condensation is indicating that those places are colder than anywhere else in the house (i.e. fastest rate of heat loss per unit surface area), and mould can be a threat to health too.
All other things being equal, start at the top
If you start at the bottom, you'll still have cold draughts coming down the stairwell anyway, and heat will just go straight up and out the downstairs living area. Insulating lofts is fairly easy (compared to insulating walls or double/triple glazing windows), cheap, and has big big savings. You might be able to turn off heating at the very top of the house, and just let rising heat do the job.
Attic room
In this case, there's no loft to insulate, so insulating the roof becomes an altogether messier job. Assuming it's plasterboard on rafters, you could make a couple of small holes in the plasterboard and shine a light through, to look at the state of the insulation between the rafters. If it's not good, you might have to take the ceiling down, pack new insulation in (eg Kingspan K7 [pdf]), then stick some insulated plasterboard over the top (e.g. Kingspan K18 [pdf]).
Do floors when you replace the carpets.
If you're going to put down new carpets, get the floor under them insulated first. Once you've got new carpets in, you probably won't want to pull them up for years, so insulate before they get laid.
But be warned!
A lot of old British houses contain decades of botch jobs, which creates lots and lots of work when you start renovation, as Jack Kelly found out (warning - contains images that anyone contemplating retrofitting a UK Victorian dwelling may find harrowing)
