Q:

What is a bull put spread?

When someone in the stock market says they are going to do a bull put spread, what does that mean, and what services do they use to do it?

A:

Bull means the investor is betting on a rising market.
Puts are a type of stock option where the seller of a put option promises to buy 100 shares of stock from the buyer of the put option at a pre-agreed price called the strike price on any day before expiration day.  The buyer of the put option does not have to sell (it is optional, thats why it is called buying an option).  However, the seller of the put is required to make good on their promise to the buyer. The broker can require the seller of the put option to have a deposit, called margin, to help make sure that they can make good on the promise.  
Profit... The buyer can profit from the put option if the stock price moves down substantially.   The buyer of the put option does not need to own the stock, he can sell the option to someone else.  If the buyer of the put option also owns the stock, the put option can be thought of like an insurance policy on the value of the stock.  The seller of the put option profits if the stock price stays the same or rises.  Basically, the seller comes out best if they can sell put options that no one ends up using by expiration day.
A spread is an investment consisting of buying one option and selling another.
Let's put bull and put and spread together with an example from Apple.
So, if you believed Apple Inc. AAPL (currently 595.32) was going up or staying the same through JAN you could sell the 600 JAN put and buy the 550 put.  If the price rises beyond 600, your profit would be the difference in price of the puts. 
Let's explore this a little deeper (prices from google finance 31 Oct 2012):
    Sell 600 JAN AAPL put @37.00     $3,700 
    Buy  550 JAN AAPL put @16.65    -$1,665
===================================================
    TOTAL                            $2,035

Worst Case:  AAPL drops below 550.  The bull put spread investor owes (600-550)x100 shares = $5000 in JAN but received $2,035 for taking this risk.
EDIT 2016: The "worst case" was the outcome in this example, the AAPL stock
price on options expiry Jan 18, 2013 was about $500/share.
Net profit = $2,035 - $5,000 = -$2965 = LOSS of $2965
Best Case:  AAPL stays above 600 on expiration day in JAN.
Net Profit = $2,035 - 0 = $2035
Break Even:  If AAPL drops to 579.65, the value of the 600 JAN AAPL put sold will equal the $2,035 collected and the bull put spread investor will break even.
Commissions have been ignored in this example. 

