soup = BeautifulSoup(
    '<p>Blah blah blah <a href="http://google.com">Google</a></p>')
for a in soup.findAll('a'):
    a['href'] = a['href'].replace('google', 'mysite')
print(str(soup))
BeautifulSoup - modifying all links in a piece of HTML?