How do you store the password? Very carefully.
In particular, I suggest using a special architecture:
Set up a separate machine, which will exist only for storing the cleartext passwords. It should be hardened and locked down as tightly as possible. You should limit the number of administrators with access to this server. And this server should be used only for this purpose. Let's call this the "login server".
The login server should export a simple API, with a few functions: (a) add a new username/password pair for some website to the password store, and return a handle that uniquely identifies this; (b) login to the third-party site using a particular username/password pair (as specified by its handle), issue a particular request, and return the response; (c) delete a particular username/password pair (as identified by its handle). Passwords should be stored on the login server (not on a shared database).
Notice that there is no API to export a username/password pair from the password store. That is on purpose. The login server should act as a Hotel California for passwords: passwords go in, but they never come out.
The login server should keep detailed logs of all uses of its passwords. You might also want to have it to some rate-limiting (e.g., notify an administrator if the rate of uses exceeds some threshold). And you might want to have some garbage-collection, so that if a username/password is not used within 90 days, you delete it from the password store, to limit the number of old passwords stored (the user can be prompted to re-enter their username/password when they next log in).
This architecture isolates the most security-critical aspect into a separate piece, the login server, and tries to keep its functionality as simple as possible, so that you can minimize the chances of security vulnerabilities that might allow access to users' passwords.
Second, I suggest that you plan to do an extra level of code review and testing, given the critical nature of the login server:
Have a second developer review all of the code for the login server, to check that it does not contain any security vulnerabilities.
Consider hiring someone to do a pentest or a security code review of the login server.
Even if you take all of these steps, you are still subject to some risk. There is no silver bullet. If the login server gets hacked, all of your users' passwords will be disclosed, which is very bad. Therefore, be as careful as you can.