I just found some Eridium, and thanks to this question I have some leads on how to find more. The pop up says it can be spent at the "Black Market". Is that a literal or figurative place? How do I get there?
You can spend Eridium once you get to Sanctuary. Crazy Earl runs the black market. It's not hidden or anything: it's just one of the stores available in town.
Once you've bought everything from Crazy Earl; there is a boss monster, Terramorphous, that will cost 4 Eridium to fight again. (source)