SQL Add to Multiple Tables

I'm pretty new to the database world and I've run into a mental block of sorts. I've been unable to find the answer anywhere. Here's my problem: I have several tables and everything is as normalized as possible (as I've been lead to understand normalization.) Normalization has lead to some challenges though. Namely, how do I do an effective INSERT? So, let's say I have tbl_Customers, tbl_Addresses, tbl_States and tbl_Cities. Now if I want to add a new customer, with their own address and everything, I'll have to check tbl_States and tbl_Cities to see if the state and city already exist. If they do then set the FK in tbl_Address with them, otherwise do INSERTS on tbl_States and tbl_Cities. I could do all this in Perl but it's horribly ugly, inefficient and just feels wrong. From what I've read/heard though, I should be able to create a sotred function where I can just CALL AddCustomer(FName, LName, Street, City, State) and it would handle all that in the background. Any suggestions? Obviously the solution will onvolve multiple INSERTs but I know there has to be a better way than what I'm doing. Here's some of what I've come up with so far but without any luck.

CREATE PROCEDURE Insert_Big(IN in_FirstName   VARCHAR(40), 
                            IN in_LastName    VARCHAR(40), 
                            IN in_NickName    VARCHAR(40),
                            IN in_BirthDate   DATETIME,
                            IN in_Country     VARCHAR(40),
                            IN in_State       VARCHAR(40),
                            IN in_City        VARCHAR(40),
                            IN in_Street      VARCHAR(30),
                            IN in_HouseNumber VARCHAR(15),
                            IN in_EmailAddy   VARCHAR(255),
                            IN in_Phone       VARCHAR(30),
                            IN in_Company     VARCHAR(40))
    BEGIN
    DECLARE Found INT DEFAULT 0;

    SELECT Found FROM tbl_Cities WHERE CityName = in_City;
    IF Found = 0 THEN
        INSERT INTO tbl_cities (CityName) VALUES (in_city);
        SELECT LAST_INSERT_ID() AS CityRow;
    ELSE
        SELECT CityRow = CityID FROM tbl_Cities WHERE tbl_Cities.CityName = in_City;
    ENDIF;

Your suggestion is good, but let's first see of we can understand your problem. Is the input data clean: is the origin of your data a source where prepopulated combo-boxes are used? If so, then your query will be a simple INSERT statement where FK relations are observed by default. If the source could be from anywhere, then you are likely to need multiple SQL statements, each checking the presence of the fields which are referenced. Hope this helps