For this you can use POSITION() or LOCATE() (they are synonyms)

SELECT   nome
FROM     pessoa
WHERE    LOCATE( 'p', nome ) > 0
ORDER BY LOCATE( 'p', nome );

Explanation: Position returns the numeric position of the substring in the desired string, effectively ordering the proximity of 'p' to the left end of the string.

Manual:

  

link

The important thing here is this part:

ORDER BY POSITION( 'p', nome );

In order to know if 'p' is in the string, you could use a LIKE or other function.

Alternative if you want to also list those that do not have 'p':

SELECT   nome
FROM     pessoa
ORDER BY LOCATE( 'p', nome ) = 0,
         LOCATE( 'p', nome );

See both working on SQL Fiddle .

Select all that begin with the letter P

SELECT * FROM suatabela WHERE coluna LIKE 'p%'

Middle letter

SELECT * FROM suatabela WHERE coluna LIKE '%p%'

Starting with letter P

..... ORDER BY CASE WHEN LEFT(NomeColuna, 1) = 'P' THEN 1 ELSE 2 END, NomeColuna

Starting with letter P and then letter P in any position

 .... Order by case WHEN LEFT(NomeColuna, 1) = 'p' then 1 else 2 end
       , case when NomeColuna LIKE '%p%' then 1 else 2 end

or ordering better

.... Order by case WHEN LEFT(NomeColuna, 1) = 'p' then 1  else 2 end
   , case when NomeColuna LIKE '%p%' then 1 else 2 end, NomeColuna

  

Nothing was said for the other records that do not contain the letter P , so I assumed they should be listed last. SQL Fiddle Example

You can do this in different ways. I'll show you two methods: 1 - Through Union

Select Nome,1 as ordem from tabela where Nome like 'P%'
union
Select Nome,2 as ordem from tabela where Nome like '%p%'  and Nome not like 'P%'
order by ordem, nome

The first Select brings the names that begin with P and we add a fixed field with heat 1.
The second Select has names that have P in any position and do not begin with P.

Then just do union and sort by the field Ordem and Nome

See working in SQL Fiddle example 1 .

2 - Using Case in the Order By clause

Select Nome from tabela where Nome like '%P%'
order by case when left(nome,1)='P' then 1 else 2 end, nome

First we select only the names that have the letter p in any position and then we create a sort criterion using the Case. For names that have P in the first position the value is 1 if not 2.

See working in SQL Fiddle example 2 .

Note:

Contrary to what has been said in other answers like '%p%' does not return names that have P in the middle of the word. This comparison brings the names with P in any position. See: SQL Fiddle Example 3