The cost of your deployment is based on 5 things, with a 6th affecting the estimated cost of deployment:
The flat fee of 32k gas. The CREATE op code, which is called during contract creation, costs a fixed 32k gas. This is of course on top of the 21k gas of a normal tx. Note: During contract creation from an EOA (non-contract address), the CREATE opcode isn't explicitly called. The return value of the tx is actually used to create the contract, but the fixed 32k fee is the same.
The amount of bytecode in the compiled contract. More bytecode means more storage, and each byte costs 200 gas. This adds up very quickly. Note that inherited parent contracts are also included in the bytecode.
The TX data. All the bytecode your sending as tx data costs 68 for non-zero bytes and 4 for zero bytes.
The code actually that runs before creation of the contract, e.g. the constructor of the contract. If the constructor requires a lot of computation to generate the bytecode, then it'll be extra expensive. Note: You'll be paying for state writes/reads that happen in your constructor here, and those can be expensive
The gas price. The higher gas price you use, the higher it'll cost. See ethgasstation.info for good gas prices to use right now. At the time of writing, 2 gwei is a quick gas price to use.
Gas limit. Let whatever tool you're using for deployment estimate this for you, and then bump it up some. It'll return the unused gas, but just make sure you supply at least how much gas it needs or it'll fail and you'll still pay for the gas.
Overall if you were deploying a contract with a simple constructor and 5k bytes of compiled bytecode, you'd be paying roughly:
CONTRACT CODE 5k*200
ESTIMATED NON-ZERO TX BYTES 5.5k*(.95*68)
ESTIMATED ZERO TX BYTES 5.5k*(.05*4)
This comes out to ~1.41 million gas, which is less than $5 USD right now. Gas prices were 20x what they are now a couple weeks ago, so you could have paid $100 for the same contract creation.
You can read more about the bytecode based costs in the yellow paper
If you need help optimizing contracts, I'd be willing to help, but not for free.
Edit: Added #3 between #2 and #4
Edit 2: Fixed numbers and subsequent math for non-zero txdata cost (64 => 68)