The same way gold or any commodity did, the person buying bitcoins valued the idea or thought it had potential and payed someone money for their bitcoins. Price is what people are willing to pay anyways. Mining is the same concept, miners are paying with their hashing power (it isn't worthless!) to the bitcoin network.
It was as shabby and undocumented as possible I'd assume, see the infamous btc pizza, some guy posted a thread on bitcointalk (you can get records of this transaction and others by going through histories) saying he wanted to pay for pizza with btc. A guy in England agreed and paid with CC for the pizza to be delivered while the other guy sent btc in exchange.