OpenSSL is a good place to start looking. It supports a very large number of secure encryption algorithms that you can use to encrypt the plain text passwords. AES-256 or Twofish are good algorithms to start looking at. 3DES is also considered sufficient to today's standards.
For good security, you will need to encrypt each user's password with a different key; that is each user has a unique encryption key to them and you do not use 1 key for all passwords. This could be a hash of the user's password that they use on your site, but often user passwords aren't strong, and if they forget the password to your site/service, then they also lose their encryption key.
For the greatest security, you shouldn't store the encryption keys anywhere. When the user logs in with their password, you can generate the encryption key in memory based on their password. Ideally it would not just be a hash of their password, but their password applied through some sort of transformation algorithm.
If that isn't an option, then you should store the encryption keys on a different physical server than the one that stores the encrypted user passwords. The server that stores the encryption keys should have a number of security and access control features in place with very controlled database access so pretty much only your application can access the keys.
And on top of that, you must disclose in your privacy policy that you may store encrypted forms of their passwords for use with the 3rd party service.
Hope that helps. OWASP may have some other helpful information related to what you are going to do.