Vineeta,

So, I think this is what makes authentication protocols like OAuth so nice because indeed they don't "store your credentials".

Lets list out some options and evaluate their security:
1) private static final String password = 'blah';
Who can see this? If you code is unmanaged customizations, anyone with Customize Application can see code for unmanaged classes. 
2) Hierarchy MyCustomSetting__c.Password__c Text field
Of course! This makes so much sense, right? In the sense that each user, profile, or whole org can have their own credentials for an external service, it's great. Problem is, it's just as visible as the code (if not more so, since it's less gobblety-gook to a non-developer sitting in the List View of Custom Setting records).
3) SObject MyExternalService__c.Password__c Encrypted Text field
This is honestly your most secure bet. With an SObject, you get sharing, field level security, as well as page layout inclusion to hide this on top of the encryption.

What does text level encryption entail? I'm sure that's Google-able. :-) But I think your intention was to find the right way to go in this scenario.

Sorry the answer came so late! I was just running into this scenario and imagined my password being visible in the Manage section of Custom Settings :-)

Cheers,

Nathan