How does one 'override' string used in a core file?
For overriding a few text strings the easiest way is probably to use the String Overrides module:


  Provides a quick and easy way to replace any text on the site.


UPDATE

The line that sets this particular string is:

$block['content'] = t('Already a member? !login', array('!login' =&gt; l(t('Login'), 'user')));


Once it's built up, the string will actually look something like this: 

'Already a member? &lt;a href="/user"&gt;Login&lt;/a&gt;'


That's why you're having difficulty targeting it with the string overrides module at the moment. If you're not developing a multilingual site you might just get away with inspecting the &lt;a&gt; tag in the block, and using that HTML in string overrides. I'm pretty sure it'll work.