Getting Started:

Layout plugins are one of the simplest and most powerful sections of the Panels API. There are two different ways that a layout can be implemented via Panels. Panels supports both module and theme implementations of Panels. The module implementation requires that hook_ctools_plugin_directory define the directory in which your layout plugins exist. (This same hook defines the directory for all Panels plugins) Alternately, if you intend on implementing a layout in a theme this can be done primary through the theme's info file. The CTools help does a great job of actually explaining this portion of the API ctools: plugins.

For purposes of this example, our module name is going to be "layout_sample" and our plugin will be "first_layout".

Directory Structure:

We're going to assume that you've laid your directory structure out very similarly to how panels does it. Something like this is rather likely: 

layout_sample
  layout_sample.info
  layout_sample.module
  plugins
    layouts
      first_layout
        first_layout.css
        first_layout.inc
        first_layout.png
        layout-sample-first-layout.tpl.php
The name of our .inc file is going to be the key to the entire layout plugin.

The .module File:

First, declare where your custom layouts reside by implementing the CTools hook hook_ctools_plugin_directory(): 

/**
 * Implements hook_ctools_plugin_directory().
 */
function layout_sample_ctools_plugin_directory($module, $plugin) {
  if ($module == 'panels' && $plugin == 'layouts') {
    return 'plugins/layouts';
  }
}

The .inc File:

We will start with the first_layout.inc file as it's the most important file we're dealing with here. First_layout.inc will look similar to the following: 

  $plugin = array(
    'title' => t('First Layout'),
    'icon' => 'first_layout.png',
    'theme' => 'layout_sample_first_layout',
    'css' => 'first_layout.css',
    'panels' => array(
      'main' => t('Main region'),
      'right' => t('Right region'),
    ),
  );
The include file defines all the other files that our layout will utilize in order to be truly useful. The array is fairly self explanitory but for the sake of specificity:
  1. Title:
    The title of our layout. (Utilized within the panels administration screens)
  2. Icon:
    The graphical representation of our layout. (Utilized within the panels administration screens)
  3. Theme:
    The template file of our layout. (Sharp eyed readers will note that the theme definition utilizes underscores instead of dashes, and does not have ".tpl.php" after it. This is referring to the layout-sample-first-layout.tpl.php file all the same, it is simply how the naming convention works. Utilize dashes in the tpl file name and underscores when referring to it in your include file.)
  4. CSS:
    The css file to be utilized for our layout. (Utilized within the panels administration screens, AND when viewing the actual panel itself.)
  5. Panels:
    Defines all the various regions within your panel. This will be further utilized within our tpl.php file.
There are many additional properties that can be added to the include file. For purposes of this document we'll also make mention of the 'admin css' property. 'Admin css' is especially useful when utilizing a fixed width layout with fixed with panel regions. This can break under most administrative circumstances, and panels provides you with the ability to give an additional css layout for the administrative section. It's a simple nicety and looks like this: 
  $plugin = array(
    'title' => t('First Layout'),
    'icon' => 'first_layout.png',
    'theme' => 'layout_sample_first_layout',
    'css' => 'first_layout.css',
    'admin css' => 'first_layout_admin.css',
    'panels' => array(
      'main' => t('Main region'),
      'right' => t('Right region'),
    ),
  );

The tpl.php File:

The tpl.php file is very similar to any other template file within drupal. The difference here is that we're being passed an array of regions through $content, and we also have a css id available to us for the entire panel in the form of $css_id. The template is very straight forward and will look similar to the following: 

<div class="panel-display panel-stacked-twothirds-onethird clearfix" <?php if (!empty($css_id)) { print "id=\"$css_id\""; } ?>>
  <div class="panel-panel panel-col-first panel-region-main">
    <div class="inside"><?php print $content['main']; ?></div>
  </div>

  <div class="panel-panel panel-col-last panel-region-right">
    <div class="inside"><?php print $content['right']; ?></div>
  </div>
</div>
This is simply an example of what the html could look like. You can alter an update this html to fit your own needs.

The Other Files:

The css and png files are as simple as any other css or png file you've ever utilized. Panels provides some images for its graphical representations of its layouts. I would heavily encourage you to modify these to suit your needs. The CSS files (admin and non) will be included at the appropriate times. Simply set them up to fit your purposes. If you're utilizing fixed width panel regions it's probably smart to provide an admin css file as well with your panel layout.