Every template file in Drupal can be overridden - as long as you know the proper naming conventions.

For panel panes, your template file should be named:
panels-pane--[pane type]--[pane subtype].tpl.php

Sometimes determining the pane type and sub-type can be difficult, so here's a tip on how to get the correct names for your template files, every time.

For starters, you'll need to figure out your pane type. I usually do this by placing the following code in my theme's template.php file*:

function YOURTHEME_preprocess_panels_pane(&$variables) {
  dpm('type: ' . $variables['pane']->type);
}

Flush your theme registry (or all caches) so that this new preprocess function is located.

Refresh the page where you can see the panels content type that you'd like to override.

You should see a bunch of messages appear at the top of your screen.

Usually, just by scanning this list you'll be able to determine which type of pane you'd like to override. For the sake of this example, we'll say the search "block" was added to a panel, and we'd like to override the search panel pane template file.

Next, add an if statement for your code to identify only the panes with the type you've identified as your block. Comment out the dpm line that printed the type, and instead print the sub-type:

function YOURTHEME_preprocess_panels_pane(&$variables) {
  // dpm('type: ' . $variables['pane']->type);
  if ($variables['pane']->type == 'block') {
    dpm('subtype: ' . $variables['pane']->subtype);
  }
}

Refresh your page again (no need to rebuild the theme registry this time) and you should see a list of sub-types that only relate to the type you previously identified, and now you can construct your template override.

In this case it is panels-pane--block--search-form.tpl.php

PRO TIP: It's also SOMETIMES** possible to construct your template file name based on the classes printed in the default content pane. The default search pane has the following opening tag:

<div class="panel-pane pane-block pane-search-form">

The second class pane-block indicates that the pane type is block.

The third class pane-search-form indicates that the sub-type is search-form

So just by looking at the classes on this content pane, you can construct the template override as panels-pane--block--search-form.tpl.php

Don't forget to remove the pane- from the start of both the second and the third class when constructing your template file name.

* any use of the dpm() function will require that the devel module is turned on, and appropriate permissions are granted.

** Note that all classes use hyphens, and sometimes types and sub-types use underscores instead. The first method here is sure-fire to get you the correct name for templates. Using the classes can be unreliable.