I've googled UART, ISP, I2C, and such. I still only understand serial and parallel as black and white. From my understanding, UART is a serial bus that sends and receives through shift-registers?
No, UART, or USART, as it is named in the AVR, is a piece of hardware for driving a class of serial buses, the RS232 bus being the most prominent. In case of the AVR the U(S)ART is build into the AVR. While in the old days it was a separate IC. This article
http://en.wikibooks.org/wiki/Serial_Programming/Typical_RS232_Hardware_Configuration explains the principles. The article is not AVR specific.
The presence of a UART in some setup typically indicates you can at least do RS232, maybe other similar buses, too. But as you can see in the mentioned article, having a UART is not enough. While the other stuff, baud rate generator and the like, is e.g. build into an AVR, the required level converter is not.
The data would need to be temporarily stored due to its asynchronous nature.
Synch and asynch just describe where the clock for the bus is derived from. Synch means the partners in the communication are synchronized via a separate clock signal. Asynch means they synchronise each other from the data signal.
It is not the asynchronous nature that requires the storage. It is the serial one, the need to convert a piece of data, a byte, into a series of bits, to be send over the serial bus one after the other. Because you send the bits one after the other, and not all at once, you need to keep (store) the bits until it is their time to be sent.
When a device claims to have "serial I/O", does it mean that it will always work with UART as long as the logic levels and baudrates match?
No, "serial I/O" is a generic term. It can mean all sorts of serial buses, protocols and voltage levels. You have to derive from the context if they are talking about a specific bus, e.g. often they mean RS232, but maybe with TTL level only, or they mean SPI, or I2C or whatnot if they just talk about general capabilities.
Some products, such as sensor modules, only mention "serial" and don't claim it to be synchronous or not.
Synch or asynch is not the key issue here. The bus type as such is. Synch or asynch is just one property of many a particular bus has. If you know the bus, you now if it is synch or asynch.
To identify the bus you need to read the data sheet. One thing to keep in mind is that several serial busses, like I2C or SPI were or are proprietary. Sometimes only the name of the bus is a trademark. Device manufacturers try to avoid license fees by implementing a "compatible" bus, and not mentioning the trademarks in the documents. E.g. I2C is often called TWI, because Philips/NXP owns (owned?) I2C. So it helps to know the alternative names, and it helps to know how a particular bus functions, to be able to recognize it in a datasheet.