Its sad to say but I've been a member of Drupal.Org for nearly 3 years and only yesterday did I submit my first patch. And it was easy. Here's a step by step list to take the mystery out of it and help you start sooner.
(Lorem Morbi: Everything I know I learned from those great people at Node One)

How to Create a Patch

• STEP 0: ASSUME THE BASICS:
  This tutorial assumes you know PHP and have GIT installed on your computer, and like myself, barely know how to use either.
• STEP 1: FIND A PROBLEM:
  In this case I was using a nifty module called Style Guide which output a variety of HTML tags for convenient CSS editing and reviewing. Style Guide had <p>, <a>, <table>, <p>, status messages and lots more, but they had forgotten the <blockquote> tag.
• STEP 2: FIX IT:
  In this case I looked at the code and saw that it was a relatively easy fix of adding a few lines to the code.
  
  <?php
// file: styleguide.styleguide.inc 
  $items['blockquote'] = array(
    'title' => t('Blockquote'),
    'content' => '<blockquote>' . styleguide_paragraph(2) . '</blockquote>',
    'group' => t('Text'),
  );
?>
• STEP 3: CREATE A PATCH FILE
  
  1. Download a clean version of the module:
     drush dl [module-name]
  2. Create an empty git repository in the root folder of the module:
     git init
  3. Create initial (clean) commit:
     git commit -m 'Initial commit'
  4. Make your changes.
  5. Commit your changes:
     git commit -m 'Things i've changed message'
  6. Create patch file:
     git diff --no-preifx HEAD^ HEAD > my_patch_file.patch
     It should look like this:
     
     <?php
//This not a PHP file. But the PHP header forces the CODE filter to make it all pretty.
diff --git styleguide.styleguide.inc styleguide.styleguide.inc
index 5868055..b11b60f 100644
--- styleguide.styleguide.inc
+++ styleguide.styleguide.inc
@@ -52,6 +52,11 @@ function styleguide_styleguide() {
     'content' => styleguide_paragraph(3),
     'group' => t('Text'),
   );
+  $items['blockquote'] = array(
+    'title' => t('Blockquote'),
+    'content' => '<blockquote>' . styleguide_paragraph(2) . '</blockquote>',
+    'group' => t('Text'),
+  );
   $items['image-horizontal'] = array(
     'title' => t('Image, horizontal'),
     'content' => theme('image', styleguide_image('horizontal'), t('My image'), t('My image')),
?>
• STEP 4: SUBMIT YOUR PATCH
  (Now this is the important part) Create a new issue on the module page. In this case it was - drupal.org/node/add/project-issue/styleguide. Your new issue should then have the Needs Review status to alert the project leader that no only did you create an issue but you've proposed changes to address it as well.
• STEP 5: PAT YOUR SELF ON THE BACK
  Done! Now it's time to find your next patch.