In a nutshell

Gas is the execution fee paid for transactions on the Ethereum network.
Its price is expressed in ether and it's decided by the miners.
The operations have a gas cost to be executed.
The miners decide the gas price, which is the price of one unit of gas.
Fee = total gas cost x gas price.

Getting more technical...

Gas is the name of a special unit on the Ethereum protocol.
It measures how much "work" an action or set of actions takes to perform.
By requiring that a transaction is paid for each operation it performs (or causes a contract to perform),
we ensure that the network doesn't become bogged down by performing intensive work that isn't valuable to anyone.

The gas unit

This is a unit that things can be measured in, but there isn't any actual token for Gas.
Ex: you can't own like 1000 units of Gas (unlike the NEO Gas, that actually is a token).
Gas exists only inside of the Ethereum Virtual Machine as a count of how much work is being performed.
When it comes to actually paying for gas, the transaction fee is charged in Ether (ETH).

But why not charge in ether directly?

Because of the volatility of the ether price.
Ether, like Bitcoin and the majority of the cryptocurrencies has a volatile price on the market.
The cost of computation doesn't go up and down just because the price of Ether changes.
So, it's helpful to separate out the price of computation from the price of a unit of Ether.
This way, the cost of an operation doesn't have to be changed every time the market moves.

Gas cost

Amount of work that goes into something (like number of hours of labour).
Analogy: timesheet of work performed by the miners.

Gas price

Is the price of one unit of gas. It is defined by the miners.
To see the current gas price in Gwei (1 Gwei = 1,000,000,000 Wei or 0.000000001 Ether), go to https://ethgasstation.info/.
Analogy: hourly wage you pay the miners to do some work you.

Fee = gas cost x gas price

This defines the price in ether of a transaction on the network.

Difference between "not having a high enough fee" and "transaction running out of gas"

If the gas price you set to your transaction is too low, no one will even bother to run your transaction.
It will simply not be included in the blockchain by miners.
Analogy: offering less money than a worker is asking to do some job.

On the other hand, if provided gas price is acceptable and the transaction results in so much computational work
that the combined gas costs go past the amount attached as a fee, the gas counts as "spent".
In this case you don't get it back to your account.
The miner will:

1. stop the transaction
2. revert any changes it made
3. ...but still include it on the blockchain as a "failed transaction", COLLECTING THE FEES from it.

Sounds unfair?
Remember that the miner spent computational power (electricity) trying to execute your transaction.
Hence, is fair that you pay them for the work they did, even though your "badly designed transaction" ran out of gas.

Providing too big of a fee

It's like providing a high Bitcoin fee for a transaction:
your transaction will be prioritised on the transactions pool, but your money is gone.
Analogy: paying a person more money just because you want. They will gladly accept it ;)

Normal gas price + more ether attached than needed

Here you just attached more ether than was needed to pay for the gas that your transaction consumed.
The excess will be refunded to you.
This is because the miners only charge for the work they actually do.
Analogy: paying a $ 50 restaurant bill with $ 100. They will just give you the change.

How to get Gas to pay for transactions?

Since the fee in gas is paid in ether you just have to add (real) ETH to your account.

Conclusion

This system makes sure that nothing runs forever.
People then are careful about the code they run.
It keeps both miners and users safe from bad code.

More details:
Ethereum Gas by ConsenSys
Operation Blockchain