"We are looking for a waitress."
"Poszukujemy kelnerki" is a correct alternative. Particularly, when the context is a job interview.
The verb "szukać" needs Genitive (kelnerki), although many native speakers mistakenly use Accusative, just like you did. It doesn't change the fact that it's wrong.