Well, firstly, there are some typos that are preventing your code from fully working. This line, for instance: adress = input(' | Address : ') should be written with address instead (notice the double D).

To add Address as a new class, just do it as you did with Person. You can have as many classes as you want in the same file:

class Address:
    def __init__(self, address='No address defined'):
        # You could create separate fields for each part of the address, 
        # for better results in a bigger system
        self.address = address

    def __str__(self):
        return str(self.address)

You're gonna need to change the way the Person object is built as well:

class Person:
    def __init__(self, name, age, phone, address):
        # instance variables, unique to each Person
        self.name = name
        self.age = age
        self.phone = phone
        self.address = Address(address)

    def __str__(self):
        # instance variables, unique to each Person
        return "Name: {}\nAge: {}\nPhone: {}\nAddress: {}".format(self.name, self.age, self.phone, self.address)

def createPerson():
    print("\nNew person")
    name = input('  | Name : ')
    age  = input('  | Age  : ')
    phone = input('  | Phone  : ')
    address = input('  | Address  : ')
    print("Creating person...\n")
    person = Person(name, age, phone, address)
    persons.append(person)

Notice that on when overriding the __str__ method of Person, you should use format instead of concatenating strings and values with the + operator. There's an increase of performance there if you are dealing with multiple values and you also don't need to worry about problems with joining numbers with strings, for instance.

I'd also suggest that you'd use a different method for searching users. Instead of checking if a user's name startswith a key, I believe checking if the user's name contains the key is a better option, since it searches the whole string, not just the beggining:

match = [p for p in persons if key in p.name]

And finally, I've made a few changes to your entry point, to make it more intuitive to the user and prevent unwanted inputs:

def exit():
    print("Shutting down.")

if __name__ == '__main__':
    choices = { "1" : createPerson , "2" : searchPerson, "3": exit  }
    x = '1'
    while x != "3":        
        print(' (1) Create new person')
        print(' (2) Search for a person')    
        print(' (3) Quit')        
        x = input('Select an option -> ')

        if x not in ['1', '2', '3']:
            print('Please choose one of the available options.')
            continue

        choices[x]()

Of course, most of these changes are suggestions, and you can accept them or not. There are also a few other modifications that I'm sure could be done to turn the code into something more "pythonic", but those might be addressed somewhere else, by someone else, if needed. The only real answer is the one regarding turning Address into a separate class. Hope it helps :)