Is there any rhyme or reason to the way LEGO part are named? Failing that, is there any other sort of taxonomy that we can use to find specific parts?
Along the same lines, my impression is that smaller sets have larger numbers -- is there any truth to that? Is there anything that we can discern this from either part or set numbers?
Finally, where can I look up all these numbers?
Usually, the LEGO group doesn't seem to have much organisation, at least in the past. That's why you can find sets with two different numbers, or two different sets with the same number.
Now the keyword here is seem, as I suppose there was some logic to it even in the past.
But nowadays there is some logic, and even if not all of it is understandable, you can at least spot some key elements, such as:
When I was a kid and they started the 4 digits scheme, the first digit indicated the global theme pretty clearly. 8 was Technic, 6 was LEGOLAND, 77 were trains, and so on. At least for trains, they tended to use round numbers for bigger sets, ending in 0 or 5.
Now, the first digit seems to have lost its significance, and sets in the same theme are usually attributed a range of numbers, with the small set getting the lowest number. It's not an absolute rule, and I guess it depends on availability or other factors.
Sets in the 10000 range are LEGO shop exclusives. Usually, you will usually only find them on Shop@Home or in LEGO retail outlets, but not in regular toy stores.
Sets in the 20000 range were used for the BrickMaster series, with each set accompanying a BrickMaster issue.
Sets in the 20200 range will seemingly be used by the "LEGO Master Builder Academy" sets
Sets in the 21000 range are architecture sets.
Sets in the 30000 range are usually small promotional polybags
In addition, there are 7-digits numbers floating around which are probably some other form of internal numbers. For specific things without a set number, that's usually the only thing you'll find.
For parts, you have to distinguish design ID (identifying a specific mold, regardless of color) and element ID (identifies a unique design/color combination).
I don't know how design IDs were or are attributed, but it seems there is now some sequential logic behind it. Note that changes in design which don't affect the functionality (hollow bars at the bottom of 1x bricks, for example) don't usually lead to a new design number (while peeron will append an "a", "b", ... to indicate the version, LEGO doesn't do that internally).
Element IDs used to be a juxtaposition of design ID and color ID, so a Black (26) 2x4 brick (3001) would be simply 300126. These numbers are still around for parts which existed when that scheme was used. 300126 is still the element ID of a black 2x4 brick.
However, at some point (not sure when), they changed this to use a 7-digit number for the element ID, which doesn't have a relation to the design ID or color any longer. These seem to be sequentially attributed, and it could be that they share the same sequence as internal set numbers (but that's just a guess, really). There are also numbers for individual instruction booklets, which ROSCO used to scan for directly on the LEGO site.
As for where to find these, that's more difficult. You'll notice I link a lot to BrickSet, that's because I feel they do a fantastic job of cataloguing sets. Peeron has a good database too, but it's usually slower.
For parts, you'll need to go to Peeron, or BrickLink, but they sometimes differ in their numbering when the official number of a part isn't known. Note that they usually use design IDs and not element IDs, although there is some work in progress regarding that.
Of course, while internal LEGO aren't exactly public, you can find design IDs embossed in elements, and element IDs in the back of all instruction leaflets. Also, the online pick-a-brick and the customer service "replacement part" function let you browse recent sets and see what the design and element IDs are for given elements.
