How is a 'Not Found' handled

There are two different situations that can cause a 'Not Found'

1) you use the search function to look for something (like 'gibberishxxx') that appears in no post or page in your site.
2) you have a url pointing to a page that does not exist.

in case 1 a search of the database returns no values - this valid request gets a 200
in case 2 the server can't find the page and you get a 404

in both cases Wordpress returns a page to the user and follows a template hierarchy

in case 1 (a search) it looks for 'search.php' and if it doesn't exist, then 'index.php
in case 2 (a 404) it looks for '404.php' and if it doesn't exist, then 'index.php

If it gets to Atahualpa's index.php then the code at the bottom is run and a 'Not Found' is displayed

This is how it works unless you have changed the code, added a search.php or 404.php or added in a plugin that could change the processing, in that case you need to figure it out yourself.