I don’t even remember how I found them, but I stumbled across their myspace page and was hooked.
Awesomely original, crazy gypsy music, accordion(!), and that is one fantastic handlebar mustache. My personal fave is Start Wearing Purple, and it does, in fact, make me want to start wearing purple for you now.
You might like to know that the “All Songs Considered” podcast for 7/24/07 has a full recording (legal) of a Gogol Bordello concert. Soundboard recording, I believe. Good stuff. You can get the podcast off itunes.
Sweet! 
If you like Googol Bordello, I suggest giving HUMANWINE a try. My favorite song of theirs is Rivolta Silenziosa.
Our cable has this arbitrary Tivo thing called “On Demand” where you can play preselected content at your leisure that includes music videos. I heard the song “Start Wearing Purple” sometime last year and loved it.
My girlfriend OTOH hates this song with the passion of a thousand burning suns, so it can be a useful thing at times.
Try “Not a Crime” as well. That should should rate 2000 burning suns for your GF and you’ll love it.
I’m a big fan of Gogol Bordello and caught them once at a show here in Chicago. They’re live stuff is crazy fun to watch. They remind me of certain phases of The Clash.
I got into them after watching the movie *Everything is Illuminated * based on the Jonathan Safran Foer novel. The lead singer of GB played the character “Alex” and some GB music is used in the movie.
Also, the movie *Wristcutters:A Love Story * features a bunch of GB music and a character that is obviously based on the lead singer of GB (even sharing the name Eugene). I don’t know if that’s out on DVD yet, I saw it at the Chicago film festival in 2006.
My favorite GB songs are “Start Wearing Purple,” “Not a Crime,” and “60 Revolutions.” “Dogs are Barking” is fun too.
Making my obligatory jump into any thread mentioning Gogol Bordello… 
I’m actually wearing my “Gypsyficatzia of Globalizatzia” T-shirt right now that I bought at the first GB concert I ever went to, oddly enough.
Anyway, congratulations on stumbling into the fantastic world of Gogol Bordello! Please be sure to check out their most recent album Super Taranta, as well as their older stuff like Multi Kontra Culti vs. Irony, Voi-La Intruder, East Infection and Gogol Bordello VS Tamir Muskat by their side project J.U.F. Also, to really appreciate GB you MUST see them live, there is nothing like it and I don’t possess the words to describe it, just trust me that you’ll never be the same. We found some excellent video last night of their performance in Vegoose this last October that we were lucky enough to see, if you search around you can probably find it. Oh, and check out the movie Everything is Illuminated if you haven’t already…Eugene, minus his moustache, plays the lead character Alex and does an excellent job, and it’s just a great movie all around with a brilliant soundtrack.
It’s also worthy to note that the band members are all awesome, friendly people, and Eugene is even more devastatingly handsome in person. 
All right, glad I’m not the only one (but it sounds like I’m a little late to the party). From what I’ve seen of their videos, it does seem that I absolutely have to see them live to fully appreciate them. But it doesn’t look like they’ll be playing here anytime soon. 
Don’t worry; they tour pretty much constantly, around the entire world, so if they’re not playing near you now chances are they will be soon!
NailBunny pretty much, well, nailed it. You must go out and buy all their music now, Red, we say so. I saw them in Boulder in October, it tied for best show I’ve ever seen. Berserk people in unusual hats bouncing around like a brownian motion demonstration (the crowd, that is).
Start Wearing Purple was on the Warp Tour free CD a few years back and me and some friends loved it, but missed them at the tour. I found one of their CDs when a record store was closing down, worth all 199 pennies.
Alright, took me awhile but I found my favourite compilation of live clips on YouTube. Pretty accurate representation (if a little out of date).
I remember showing this video to a friend of mine who had already previously agreed to go to one of their shows with me. It pretty much scared the crap out of her. 