How should I store passwords that need to be available in plain text? Suppose I need to store login information for a third-party website for a few users, how would I go about doing it?

Since I am logging into a third party website, I need the password in plain-text, not hashed. And no, the website in question does not provide any API.

In addition, the server I am using is accessible to people whose credentials are stored on it, so they will be able to get at least one plaintext/ciphertext pair, namely their own.

Given these two conditions, is there any way of storing user credentials on the server, or should I just ask for them each time the user logs in?
You could encrypt them using some key derived from the user's password (to your site).

Of course, this assumes that you get your user's passwords in plain text (or in any form which is always the same) - thus you need to have an encrypted connection to your user. Do not allow any non-SSL login.

You can use some key derivation function like PBKDF or bcrypt to derive the encryption key from the password (if this uses a salt, make sure the salt is not the same as you are using for your password checking). You could additionally use some server-secret here, but if your say that some potential attackers have (read-)access to the server anyway, this will not really increase security.

Then encrypt/decrypt the stored login information for the third party website using a standard symmetrical encryption algorithm like AES.

Of course, you also should use an encrypted connection to this third-party website.