I am absolutely NOT an expert in this, but I can tell you our situation.

First, we have concrete, too, but not on grade (3rd floor apartment). We also used heating mats, choosing Warmly Yours. (This decision involved the claims of electromagnetic fields reduction by someone else - I can't remember which one now - and coil distance and wattage per square foot.)

I read a lot about trying to create a "thermal break" between the heating mat and our 12 inches of concrete. In the end, after reading a lot of posts all over the internet (reader beware, there is some pretty sketchy non-science out there), especially johnbridge and I think jcl, and after extensive discussions with my nephew who is a materials engineer, we did two things: 1/4" Wedi board and SuperTherm.

Here's how we got to that decision (YMMV):

So very many people told us that we didn't need any insulation, that insulation was stupid and unnecessary, that the heating mat would be absolutely fine without it. The two things we heard the most were:
1.) "I've installed 12 trillion-gazillion mats (or whatever extraordinary number they thought I would buy into), and I've never used it because you don't need it."
2.) "Heat rises."

Regarding point #1, the thermal properties of wood underlayment versus concrete cannot be understated. What works over wood will be different over heat-sucking concrete. Even if you ask if all their other jobs were over wood, they very very VERY frequently lie. (Oh yeah, and I don't care what cocked-up thing you've inflicted upon other poor unsuspecting, non-researching saps....) Wood acts more as an insulator, concrete as a conductor of heat.

Regarding point #2, lord this is stupid. Hot AIR rises, because it has more energy which makes the air molecules vibrate more, pushing the molecules apart, which takes up more room (for the same number of particles), which makes them less dense...so they rise above the cooler air. This is for AIR. When dealing with solids (and some liquids under some circumstances), heat acts more like electricity (both are forms of energy), and takes the path of least resistance. Meaning, that the heat from your mat will travel EITHER UP OR DOWN according to whether the concrete or your tile is more resistant to heat energy.
The science behind which material involves density, heat capacity, etc. (It isn't exactly like electricity though, in that it isn't an all-or-nothing path decision. Apparently, with heat and different materials, it is a matter of what percentage - I'm over simplifying here - goes in which direction. Think about it: electrical conducting shields work absolutely, no matter how long the wire is live, but heat shielding can only slow down the transfer.)

For anyone who owns a frypan with a handle that is made of a different metal than the pan body itself, this concept is in that pan. The body of the frypan is designed to transfer heat fast, the handle is made from a different metal that will absorb heat more slowly. The point: the handle WILL get hot eventually, just a matter of how much time.

My nephew (a materials engineer, who doesn't work in this field but had more game than me for running the equations) figured out that my tile is waaaayyy more resistant than the concrete, that 70% of my heat would go into the concrete and only (about) 30% into the tile. All the people that said bare concrete would be "fine" were kind of technically sort of right: my tile would eventually absorb some amount of heat.

I had two issues with this: how much more energy would I be paying for to heat the 12 inches of concrete AND how sloooowww would my tile heat up without insulation? So no contest, we needed a thermal break.

(I wanted to be able to get my tiles warm in - at most - a couple hours. Without insulation, the mats would have to turn on about 12 hours ahead of time, just to hit 80 degrees by morning. No way.)

I found a thread on johnbridge where somebody (I can't remember his screen name but I remember his real name is Eric, if that helps) actually mocked up several underlayment materials and measured how long it took for the top of the tile to move something like 20 degrees. (This was a while ago so some of these numbers might be a bit off, but the gist is the same.) So a good insulator would allow the tile to heat up faster because more heat is going up rather than down. He tested a couple products, and the clear, hands-down winner, coming in 40% less time than any of the others, was Wedi. (Interestingly, there was very little difference between the 1/4" and the 1/2". The guy that ran the test didn't understand why there wasn't a significant difference either, but we're talking about tenths-of-a-point level of small difference.)

We went with 1/4" Wedi.

The other thing we did - which was probably overkill - was because there are three different kinds of heat, and my nephew wanted to experiment with a ceramic (anti-reflective, anti-radiant) paint substance he read about. I understand the theory (waaayyy too involved to get into here), but the proof of this substance (SuperTherm) is not anywhere near substantiated yet. And dealing with the company sucked pretty badly (very unprofessional and difficult). But it is on half of my bath floor (we did a bunch of test to make sure it would adhere sufficiently to not screw up the tile) so I guess we'll see. The bath hasn't gone live yet and probably won't for another month.

Don't let anyone tell you that you don't need it. Yes, the mat will work without insulation, but how well? How fast?

(Yes, we are on a programmable timer. This was a big arguable point for the you-don't-need-no-stinkin'-insulation crowd, that the timed thermostat would cure all. That's fine as long as there are no exceptions to the original timer programming. But let me tell ya', my husband is ALL about exceptions. I swear he stays up late at night, trying to think up new ways that our routine won't suffice. He's adorable, but I need flexibility - in both lunch menus and floor temp.)

I know this post is long, but your question involves some actual science (chem and physics), and knowledge is power, no matter what path you choose. And the amount of mis-information out there is staggering. And the surety with which people will tell you bad information is daunting. (And arrogant. And ignorant.)

In answer to your other questions:
As state above, we went with Warmly Yours. The pre-sales service was outstanding, they help you every step of the way, even designing the layout of the wires (which you can make a complete cock-up of if you don't pay attention). And they're awfully nice.

Insulation goes over the concrete and under the mat. Thinset is NOT an insulator.

We used a self-leveling products after setting the wires. I was scared that we'd never ever ever get our little mosaics flat if we didn't do this. From what I've read, some people do the SLC as a matter of course.

I'm not sure I'd be brave enough to lay the wire and the tile all in one step, as some mat providers claim you can. It seems like it would lead to an inevitably wonky floor. Or that was just my fear.

Thanks a lot, Tuesday. I am going with Warmly Yours as well and you are right; their support is very good. That was deal clincher for me at least.

Also I read their faqs and they clearly state that insulation is advised for concrete slabs. Therefore, I have no dilemmas as to "whether" to put insulation. My question is "which cheapest/effective one".

At their site they have listed some websites that sell cork floor and backerboards etc. I went to those sites and they quote the approx price as $7.00 per sq ft! This is more expensive than my marble tile and I am not willing to pay this price. That is what prompted me to post this question here on this forum.

Maybe I should have been more clear in my initial question: I would appreciate a suggestion of an effective heat insulator that is inexpensive and can be purchased easily (perferably at local home depot etc).

Also, I can walk in HD and ask but I would prefer to hear from folks here who have successfully tried a product and have been happy!

I am no fan of big box stores as well, however, they are the ones in the close proximity of where I live. Also, I visited a pretty high end fixtures store this past weekend and the sales guy did not seem to know much more than what the tags on the items had written on them.

Anyway, if you can send me the URL of where you got your Wedi then I would appreciate it!

I think I was referring to people who work more on the technical side. And with everything and everyone, your mileage may vary over different stores, different clerks, different days. (I just went into a granite and tile place to get samples for our threshold and the guy that helped me couldn't possibly have been less interested in helping. Maybe he knew his stuff, maybe he didn't. I'll never know because he didn't bother to share. So I get your point.)

Probably the fastest way to find out where Wedi might be in your area is to contact this guy:
Bastian Lohmann
Technical Sales Manager
mobile: 770-366-6835

I got that info off of the very bottom of this page:
http://www.wedi.de/usa/

If you decide to go with something else, I know some people have been using something called EasyMat, though I have no idea what that is besides that it is peel-and-stick.

Maybe someone else will chime in on what they used or what they know to be actually effective.