How to perform str_replace on the results of wp_list_pages

Question

Change your $child in your code to $InnerPages, like this:

$InnerPages = wp_list_pages('child_of=".($post->post_parent != false ? $post->post_parent : $post->ID)."&title_li=&echo=0');
$InnerPages = str_replace('<ul class="children">',
                               '<ul class="children"><li>Overview</li>',
                               $InnerPages);
echo $InnerPages;

You were saving your change in $child but then displaying $InnerPages which was unchanged. Additionally the class is children and not child and must match exactly to work.

Edit to accommodate comments:

If I take your output:

<li class="page_item page-item-113 page_item_has_children current_page_item"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/">Los Alamos National Laboratory</a>
<ul class="children">
    <li class="page_item page-item-115"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/online-contact-form/">Online Contact Form</a></li>
</ul>
</li>
<li class="page_item page-item-95"><a href="http://127.0.0.1/abbatech/procurement-capabilities/nasa-sewp-v/">NASA SEWP V</a></li>
<li class="page_item page-item-2"><a href="http://127.0.0.1/abbatech/procurement-capabilities/sample-page/">Sample Page</a></li>

And I apply your code, corrected according to my answer:

$InnerPages="
<li class="page_item page-item-113 page_item_has_children current_page_item"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/">Los Alamos National Laboratory</a>
<ul class="children">
<li class="page_item page-item-115"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/online-contact-form/">Online Contact Form</a></li>
</ul>
</li>
<li class="page_item page-item-95"><a href="http://127.0.0.1/abbatech/procurement-capabilities/nasa-sewp-v/">NASA SEWP V</a></li>
<li class="page_item page-item-2"><a href="http://127.0.0.1/abbatech/procurement-capabilities/sample-page/">Sample Page</a></li>
";

$InnerPages = str_replace('<ul class="children">',
    '<ul class="children"><li>Overview</li>',
    $InnerPages);
echo $InnerPages;

I get this output:

<li class="page_item page-item-113 page_item_has_children current_page_item"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/">Los Alamos National Laboratory</a>
<ul class="children"><li>Overview</li>
    <li class="page_item page-item-115"><a href="http://127.0.0.1/abbatech/procurement-capabilities/los-alamos-national-laboratory/online-contact-form/">Online Contact Form</a></li>
</ul>
</li>
<li class="page_item page-item-95"><a href="http://127.0.0.1/abbatech/procurement-capabilities/nasa-sewp-v/">NASA SEWP V</a></li>
<li class="page_item page-item-2"><a href="http://127.0.0.1/abbatech/procurement-capabilities/sample-page/">Sample Page</a></li>

So, what isn’t working?