First thing to check would be if the coolant is circulating. With the car cold, remove the radiator cap and set it aside. Let the car idle for ten minutes or so. You should see the coolant circulating and the coolant in the radiator should heat up. If the coolant isn't circulating, I think you are likely in trouble.
The cheapest cause of your problems would probably be a stuck open thermostat augmented by a cracked overflow container that allows the heated coolant to drip out on the road while you are driving. The most expensive would be a cracked block (although a leaking head gasket would be a lot more likely) and possibly a busted water pump that is preventing warm coolant from circulating to the coolant temperature sensor.
If it were me, I'd replace the thermostat and pray that somehow fixes everything.