Hai già fatto gli account? E' possibile aggiungere una persona come amico?
Come prima cosa devi fare in modo che uno possa registrarsi e che tu possa vedere il suo profilo direi, poi passa alle richieste d'amicizia. Scritto in pseudocodice l'algoritmo potrebbe essere così, una volta capito dovresti metterci pochi minuti a codificarlo in PHP:

PROGRAMMA PRINCIPALE pagina_utente
SE [SOTTOPROGRAMMA siete_amici(input id1, id2)] == vero //id1 e id2 sono gli id dei 2 utenti
ALLORA
non mostrare nulla
ALTRIMENTI
mostra un pulsante per la richiesta amico
[SOTTOPROGRAMMA aggiungi_amico (input id2)] //al click del pulsante verrai reindirizzato ad aggiungi.php
FINESE

SOTTOPROGRAMMA siete_amici [input id1, id2, output true/false]
QUERY <- seleziona tutti i valori in UTENTI dove ( (id1==ID1 && id2==ID2) || (id1==ID2 && id2==ID1) ) && AMICIZIA_ACCETTATA==1 //1 sta per vero, quindi ti ha accettato
SE RISULTATI_DELLA_QUERY > 0
ALLORA
OK <- vero
ALTRIMENTI
OK <- falso
FINESE
Far uscire OK

SOTTOPROGRAMMA aggiungi_amico [input id2, output true/false]
QUERY <- inserisci in UTENTI id1=ID1 e id2=ID2 //id1 è l'ID della persona che aggiunge l'altra come amica
SE la query è andata a buon fine
ALLORA
OK <- vero
ALTRIMENTI
OK <- falso
FINESE
Far uscire OK


Così credo che la spiegazione sia più che chiara, per il codice in PHP e MySQL dovrei sapere troppe cose, come i tuoi dati di DB ecc... Ad ogni modo non credo ti sarà difficile tradurre, se hai bisogno sono comunque disposto ad aiutarti.