I'm particularly interested in how the "Millennium" part pertains to the ship itself. It wouldn't hurt to explain the "Falcon" part either though.
The Millennium Falcon has a long history, explained on Wookieepedia and I would strongly encourage you to read it here.
The important part on that page is the below quote:
The Second Chance [the Millennium Falcon before it was rechristened] was briefly rechristened the Gone to Pieces during this operation, but when he began flying the ship for the Alliance, he rechristened her the Millennium Falcon, after the bat-falcon
Just to note, in the above quote, Wookieepedia explains that 'he' is Zenn Bien who had stolen it, however this source makes it sound like it was Quip Fargil who rechristened it the Millennium Falcon, but also agrees it was after a 'bat falcon'.
Now a 'bat falcon' was:
a swift species of flying creatures. It inspired the name of the starship Millennium Falcon.
That explains the 'falcon' part; as for the 'Millennium' part of the name, I suspect (note that I don't have any evidence for this, but I think it's a reasonable speculation) that it was named so because 'Millennium' sounded futuristic; consider when Star Wars was released - it wasn't too far from the turn of the millennium, but far away enough to make it seem very futuristic. Just my thoughts on this part, but I'll keep on looking to try and find any evidence in this regard.