Randomized algorithms and the one time pad The way I understand it, an algorithm is said to be randomized if it uses randomness as part of its logic (quoting Wikipedia). Now, in the case of encryption algorithms, I assume this means that for the same input, different outputs (i.e. ciphertexts) will be produced. The question is, what does "input" mean in this context? 

In particular, does it include only the plain text to be encrypted, or does it also include the key? To give a concrete example, is the one time pad a randomized algorithm? If it is so, then "input" must mean plain text only. 

To make matters more confusing (to me at least), again quoting Wikipedia: "To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.", where the last word is linked to the "Randomized Algorithm" page I link to in the first paragraph. So, given that the one time pad is semantically secure, is must be a randomized algorithm... right?

To add the cherry at the top of the confusion cake, there are still algorithms like, for instance, AES in CBC mode with a random IV, which will produce different outputs, when run multiple time with the same plain text, and the same key. Of course, this means that when you consider the input to one such algorithm as being the plain text only, you get the same result: different ciphertexts for the same plain text. So it would seem that the only "coherent" (lacking a better word) definition would require that input == plain text. Am I surmising correctly?
You indeed need to define what you understand by an encryption algorithm. The common way of doing this is to consider and encryption scheme as a tuple of three primitives: a key generation algorithm (upon a security level, output a randomly chosen pair of keys), an encryption algorithm to be instantiated with the generated key (that maps an input plaintext to an output ciphertext) and a corresponding decryption algorithm to be instantiated with the corresponding key.

To be semantically secure for an encryption scheme means that given an a priori information about a plaintext and the corresponding ciphertext under the encryption algorithm, no information from the plaintext can be derived that could not have been derived from the a priori information alone. (This has to be understood complexity theoretic-wise.)

Now the one-time pad encryption as you describe it does not fit the above scheme as it does not have this set of three primitives: the key (one-time pad) is to be changed for each plaintext. One could however construct a close encryption scheme this way (I assume fixed length plaintexts for simplicity, but it's not a limitation): one can see the key generation algorithm as a big table of pads indexed to somehow correspond to each one of the possible plaintexts. The encryption algorithm then lookup this table and xor it with the plaintext to produce the ciphertext. This scheme is semantically secure.

Here's is the bottom-line: an asymmetric encryption scheme has to be probabilistic since otherwise, given the encryption key (which is not the decryption key) it would be possible to distinguish, say, the encryption of the "hi bob!" message from that of the "hi alice!" message. But a symmetric encryption algorithm does not have to be probabilistic for the scheme to be semantically secure (the encryption scheme defined above is). However, if the security goal is to achieve the same for pairs of ciphertexts instead of single ciphertexts, then scheme defined above to fit the framework would not be sufficient as it would allow an adversary to distinguish between the pairs of ciphertexts corresponding to the same messages from the pairs of ciphertexts corresponding to distinct messages.

So, yes, a probabilistic encryption algorithm inputs a plaintext and outputs a ciphertext that will vary according to the random coins generated internally.