Ok so I have this (see picture (https://drive.google.com/file/d/0BxNxI7cGPepbN3lacW9heWlRQzQ/edit?usp=sharing) and the L293D heat up almost instantly when the 12V is applied and and almost burns if you touch it while the stepper heats slowly. The steppers coils are (Red & Yellow) (Grey & Green). I'm assuming this happens because the stepper has all four wires as positives. So I don't understand where I supposed to ground it so it stops overheating.
You provide no specs of the motor - this is crucial, unless the motor windings
are ~20ohms or more I'd expect the L293D to melt down.
If you have a motor with low-impedance windings you do not use a dual-H-bridge,
you need a chopper driver such as the ubiquitous A4988. Anything under 5 ohms
is definitely "low impedance".
Bipolar steppers are usually low impedance, unipolar steppers are usually high-impedance.
Each winding will draw 12 V/ 35 ohms = 342 mA, which should be well within the L293D current-handling capability. So, the wiring is probably wrong. Can you provide a clear schematic diagram of your wiring?
The other thing to keep in mind is that you may need a heatsink on the L293. If you are using the 16-pin DIP (there's also a 28-pin DIP variant - but I have never encountered one), then pins 4 and 5, and pins 12 and 13 are the heatsink/ground pins.
At one time, you could get DIP heatsinks for this chip that clipped to the chip and made contact with those pins. Other heatsinks were soldered to those pins. In other cases, the pins were soldered to larger ground fill planes on the topside of the PCB (so the PCB copper fill acted as the heatsink).
Basically - those pins are the main output for the heat of the IC when handling larger currents - so you may need to get a heatsink on those pins. You can almost forget about trying to find those heatsinks that clipped or soldered on - they are almost unobtanium today. You'll have to devise another method.
Ah, at least the motor's high impedance, its viable.
Yes, L293's and L298's are always hot, usually too hot to touch, even for
modest motors - you throw perhaps 20% to 50% of your power away in
them. Their only advantage, if they have one, is they are cheap,
but in all other respects a MOSFET H-bridge is superior.
Here you've got about 2.5 x 0.27 = 0.7W to dissipate or so, so heatsink
required (not surprizing).
(That's 2.5V lost in the darlingtons, so 9.5V / 35 ohms = 0.27A through
the windings - which get 2.5W or so). I'm assuming only one winding
on at once. If you drive both windings simultaneously the chip will
run a lot hotter.