How to tell if a house is equipped for a gas stove
Any house can be equipted to run a gas stove.  Some houses have gas service from the utility, others have on-site tanks.  

If you already have gas service or some type of gas distribution in your house, then you can add a stove by having a licensed contractor run a line to your kitchen.  The process is similar to running new pipes or electrical circuits.  It is easier to do if the area under your kitchen is not finished, otherwise expect a lot of holes.  The cost will depend on the distance from the gas main and the complexity of the run.

Cost will also depend on where you live.  Just for an example, in Toronto, ON, Canada, it cost me $700 CAD to add hook-ups for my BBQ and stove. The BBQ run was outside while the stove run was done in my unfinished basement.

Make sure you contact a licensed installer/contractor.  Don't mess with gas yourself.