Most people think just because it is a free email address with no billing address, they are safe, but there are many ways they can be tracked. Take for example the suspect in the Times Square bombing. Technology helped lead to his arrest. The car that was used was apparently purchased in cash after an ad on Craigslist. The guy was apparently somewhat clever in covering his tracks, according to reports. He switched license plates at a place where it was unlikely to be noticed (a garage - when was the last time you checked to see if your license plates are really yours anyway?). He also attempted to remove the vehicle identification number. Unfortunately, it is found in a number of places in most vehicles, and the suspect missed a few locations.
So, how did Craigslist play a role? The seller apparently got an email from the buyer, who paid in cash. With that email, authorities can determine what IP address that email was sent from. With that IP address, it's an easy matter to determine who the Internet Service Provider of the sender was, and you can subpoena that ISP to get the name of the customer.
If that was a dead end, they could also trace the email address. Let's say the guy signed up for a free Hotmail account. He signed up from some computer somewhere, so law enforcement could subpoena Hotmail to find out what computers accessed that email account, and follow the trail as mentioned above.
Now, this guy was either sloppy or just did not think they would catch up to him quick enough for things to matter, because there were a number of ways he could have obscured his identity better.
First of all, he should have created this email address from a public computer, and only accessed it from a public computer. Either that, or he should have "borrowed" someone's wireless Internet connection, because then the trail would lead back to them. He could have driven around and found one easily (and this is part of the reason not setting up security on your wireless Internet can be a very bad thing).
Secondly, he should have made sure there were no cameras that could help aid in his identification, regardless of the method. A nice, unsecured location could be helpful, and scouting is important.
Thirdly, he should have made sure to pay in cash (if this were a cybercafe), use a fake ID (in a library), or used a program to try to hide his computer's network card address (if he used someone else's Internet connection). Each network card manufactured has a unique identifier, so if he connected to my router, I could browse my logs and find out the network card address (known as a MAC address). Law enforcement could subpoena the manufacturer to get the name of the buyer. If he was smart, he would have paid cash for a cheap network card (and bypassed the built-in wireless found in most laptops) and used a throwaway one. Again, if it was purchased recently, store cameras could be used to track suspects.
Finally, he should have used some program to anonymize his Internet usage and/or mask his IP address.
I do not know the specifics of what he did or did not do right, but electronic communication is not difficult to track with a little technical knowledge and the power of a court order.
Link to Story