EDIT: Make sure to check the comment from @FallenAngel at the bottom and check for security risks in your code!
As Gordon mentioned, you should use a WHERE clause to make things easier. Like so:
import re
import MySQLdb
db = MySQLdb.connect(host="127.0.0.1", user="root", passwd="", db="sakila")
cur = db.cursor()
search = raw_input("Enter username: ")
user_regex =  # input a regex here to make sure the username matches a format which avoids SQL injection.
if re.search(user_regex, search):
    query = ("SELECT password FROM staff WHERE username = %s", (search,)) #  add a WHERE clause
    cur.execute(query)
    results = cur.fetchall()
else:
    results = None
if results:  # Now we just need to check if the queryset is empty or not.
    print("username found")
else:
    print("invalid username")
db.close()
General rule of thumb is to try and make SQL do the searching for things, it's built for it so will be faster than Python.
Make sure your username column is a primary key (or a unique one at least) so you don't have duplicates.
EDIT: Based on @FallenAngels point, you shouldn't directly inject user input into an SQL query as it would expose you to SQL injection.
EDIT2:
First note that we are no longer using "%s" % var formatting for this solution as it is unsafe! Instead we are using "%s", (var,) formatting which is for db queries.
%s (it can also be %d, %n and a few other letters) in a string is a form of string formatting used to insert variable content into a string.
Essentially if you say:
"some stuff here: %s" % var
Anything that is in var will replace the %s in the string. There are several intricacies so it's worth reading more here: https://docs.python.org/2/library/string.html