Least expensive way to boost DC voltage
There's a technique called a charge pump with which you can make a voltage doubler, but that will only give you 3V from a 1.5V cell, and even less from the 1.2V cell. I'm still mentioning it because several microcontrollers these days will work with voltages down to 2V. A charge pump can only supply limited current, enough to power the microcontroller, but extra power devices like motors or relays are out. The voltage will also drop under load. So not ideal. The LM2660 is a switched capacitor charge pump.
The better solution is a switching regulator. These exist in two major topologies: "buck" to go from higher to lower voltage, and "boost" to go from lower voltage to higher. So you want a boost regulator. Major manufacturers include Linear Technologies (more expensive) and National Semiconductor (recently acquired by Texas Instruments). The LM2623 can operate on input voltages as low as 0.8V.
About current and battery life. I'll assume you're working with 1.5V batteries. The ones here on my table are rated for 2300mAh, so let's use that value. Also let's say your microcontroller plus extras need 100mA at 3.3V. That's 330mW. If the switcher is 85% efficient that means it draws 330mW/0.85 = 390mW from the battery. That's at 1.5V, so you'll draw 260mA from the battery. The battery is rated at 2300mAh, then your device can run for 2300mAh/260mA = 9 hour on one charge.
If you plan to load the battery rather heavily, I would remain below 2300mA, which will drain it in 1 hour.
To make a higher power voltage from a battery like that takes a particular type of switching power supply called a "boost converter". This uses a inductor to make spurts of higher voltage. The concept is the same how a hammer makes spurts of much higher pressure than your arm can deliver to the nail directly.
There are chips out there that integrate much of this. Linear Technologies, ST Micro, TI, and various others make such chips. Some of the offerings from Microchip are quite nice within a narrow voltage range as you have.
Making higher voltage is OK, but these chips are still limited to the basic laws of physics. They can't provide more power out than in. Since power is voltage times current, the output current must go down as the voltage goes up. Just like with the hammer, your arm has to put in much more motion than is imparted to the nail in return for higher force out. Of course there will be some loss too. Anything over 90% is quite good. Let's say for purpose of example that your boost switcher is 80% efficient and it is making 3.3V at 100mA out from 1.3V in. 3.3V * 100mA = 330mW. Accounting for the loss in the switcher, 330mW / 80% = 413mW in. 413mW / 1.3V = 317mA, which is the current that will be drawn from the battery.
In this example, the battery current is 317mA, which is within range of what a AA type can sustain for a while. To get some idea how long the battery will last, you have to look at the battery capacity. This is expressed in current*time, like mA-hours. Let's say your AA battery has a capacity of 2 A-h. At first approximation, 2 A-h / 317 mA = 6.3 hours run time. However, there are a lot of things that mess up this basic analisys. For one thing, the current won't be 317mA over the whole discharge life of the battery. As the battery voltage gets lower, the switching power supply will draw more current. Temperature also greatly effects battery capacity. If this is meant to run outdoors in a cold environment, you might only get 1/2 or less of the rated battery capacity. The current itself effects capacity too. 300mA for a AA is probably not to the point where it degrades capacity significantly, but 1A certainly would be. You might get 2.0 A-h at 300mA, but only 1.6 A-h at 800mA. I'm making up numbers. These are probably not totally ridiculous for most AA batteries, but you really have to look at the battery datasheet yourself.
Answers given will either not work in the real world versions of what you describe or are far from lowest cost.
Steven's LM2623 datasheet is a reasonable choice and will start on 1.1V and run on 0.9V but the IC costs about 60 cents.
If you genuinely want lowest cost then a properly engineered version of the Joule Thief is a good candidate. I use that name as it will lead you to many many variants but the original form is not very efficient. However, once you have the idea you can look at the options and choose one.
The "Joule Thief" is a one transistor self oscillating boost converter using an inductor main winding plus an inductor feedback winding. For DIY use you could build one for free from almost any modern scrapped electronic device or if buying new or surplus parts could build one with 10 to 20 cents of parts.
Here is a good example of a DIY Joule Thief page
The composite image below is made of 3 images from the above page:
Others - You can build boost converters with one transistor and two separate inductors - advantage is no need for two windings. And The classic Colpitts oscillator uses an untapped inductor.
A number here and
Other versions:
Good
A few zillion others
Wikipedia:
Added:
The basic Joule thief is not a marvellous design. It's outstanding feature is that it does work in many cases, thereby introducing energy conversions, SMPS, boost converters and more to many relatively inexperienced and uneducated electronics dabblers.
Various thoughts on regulated versions can be found by looking throiugh this collection (YMWV).
I stumbled upon a few prior stack exchange Joule Thief answers that seem to have some relevance. Searching for "Joule Thief" on this site will turn up a few more.
How can I calculate a Joule Thief
alternative fix to: How can I calculate a Joule Thief
Both December 2012
Various one cell to LED drivers here