Some airports charge their own departure fee (to help fund airport operations) that is not included in the ticket price. Until about 2009 or so, this was also the case for the airport in Christchurch, New Zealand (I think it was about NZ$25). At that time they changed to include the departure fee in the ticket price for departing passengers. This makes it a ...
The airport departure fee as of August 2014 is 20 US$. I (the OP) however didn't had to pay it as it somehow was already included in the ticket price (despite the warning on the website). I got the sticker, confirming that I paid the fee, on my boarding pass at check in.
My advice: ask your airline at check in when departing from La Paz!
While visas are usually required to enter Bolivia, there is a TWOV (Transit without visa option):
TWOV is permissible for travellers continuing their trip to a third country within 24 hours on condition that they:
Have tickets with confirmed reservations.
Have all documents needed for their next trip.
Do not leave the airport.
There is ...
We went back to look for it and there really is one - on the left hand side immediately after entering departures hall.
Storing one piece of luggage for 24 hours costs 25 Bs
Note that the above information is correct as of January 2015, a new terminal is under construction and things might change once that is completed.