There Was an Old Lady
Perl&nbsp;5.10, 392 384 372 235 369&nbsp;(ASCII)&nbsp;/&nbsp;234&nbsp;(Unicode)

The shortest ASCII version of this is 369 characters long:

@_=(fly,spider,bird,cat,dog);$_="There was an old lady who!ed a";for$P("",",
That wrJand Jand jJinside her",",
How absurd&amp;",",
Imagine that&amp;",",
What a hog&amp;"){$p=$c;$c=$".shift@_;$t=$p?"She!ed the$c to catch the$p,
$t":"I don't know why she!ed that$c,
Perhaps she'll die.

$_";$_.="$c$P.
$t";s/&amp;/ to! a$c/}s/!/ swallow/g;s/J/iggled /g;say"$_ horse,
She died of course."


It started from this base program:

my @animals = qw(fly spider bird cat dog);
my $buf = "There was an old lady who swallowed a ";
for my $phrase ( "",
                 ",\nThat wriggled and iggled and jiggled inside her",
                 ",\nHow absurd&amp;",
                 ",\nImagine that&amp;",
                 ",\nWhat a hog&amp;" ) { 
  $previous = $current;
  $current = shift @animals;
  $trail = $previous ? "She swallowed the $current to catch the $previous,\n$trail"
                     : "I don't know why she swallowed that $current,\n"
                       . "Perhaps she'll die.\n\n$buf";
  $buf .= "$current$phrase.\n$trail";
  $buf =~ s/&amp;/ to swallow a $current/;
}
say "$buf horse,\nShe died of course.";


The core idea is to keep the end of the rhyme and the beginning of the next one in $trail, augmenting it as we go along.  It's made non-trivial by the need of a special case for the first use, and the attempt to re-use the animal name variable even in the animal-specific phrase.  Further optimizations include:


one-character identifiers for everything
using barewords instead of quoted strings for the animal list
use of the accumulator $_ for $buf to shorten most substitution operations even more (use of @_ is by force of habit and doesn't win anything more than any other character)
including the preceding space directly inside the animal name variable (the space character taken from the $" variable)
regexp substitution to shorten the most common phrases: ' swallow' and 'iggled '
no code spacing whatsoever and all \n in string literals replaced with actual newlines


All but the last optimization yield this:

@_ = (fly, spider, bird, cat, dog);
$_ = "There was an old lady who!ed a";
for $P ( "",
         ",\nThat wrJand Jand jJinside her",
         ",\nHow absurd&amp;",
         ",\nImagine that&amp;",
         ",\nWhat a hog&amp;" ) { 
  $p = $c;
  $c = $" . shift @_;
  $t = $p ? "She!ed the$c to catch the$p,\n$t"
          : "I don't know why she!ed that$c,\nPerhaps she'll die.\n\n$_";
  $_ .= "$c$P.\n$t";
  s/&amp;/ to! a$c/;
}
s/!/ swallow/g;
s/J/iggled /g;
say "$_ horse,\nShe died of course.";


Additionally, this golf is a victim of the underspecified encoding problem.  As it&mdash;as of now&mdash;counts individual characters instead of bytes in a specified encoding, there's a big gain to be achieved by decoding the program source from UCS2 before starting.  The final result isn't very readable anymore, but it's short all right. (234 characters, counted as a difference from perl -E'' as usual) (I had to include the trailing newline back to make it valid UCS2)

$ perl -MEncode=from_to -e'$_="䁟㴨晬礬獰楤敲Ɫ楲搬捡琬摯朩㬤弽≔桥牥⁷慳⁡渠潬搠污摹⁷桯Ⅵ搠愢㭦潲⑐⠢∬∬੔桡琠睲䩡湤⁊慮搠橊楮獩摥⁨敲∬∬ੈ潷⁡扳畲搦∬∬੉浡杩湥⁴桡琦∬∬੗桡琠愠桯朦∩笤瀽④㬤挽␢⹳桩晴䁟㬤琽⑰㼢卨攡敤⁴桥④⁴漠捡瑣栠瑨攤瀬ਤ琢㨢䤠摯渧琠歮潷⁷桹⁳桥Ⅵ搠瑨慴④Ⰺ健牨慰猠獨攧汬⁤楥⸊ਤ弢㬤弮㴢④⑐⸊⑴∻猯☯⁴漡⁡④⽽猯ℯ⁳睡汬潷⽧㭳⽊⽩杧汥搠⽧㭳慹∤张桯牳攬੓桥⁤楥搠潦⁣潵牳攮∊";from_to($_,utf8,ucs2);eval'


A good thing there was a lot to golf from before resorting to Unicode, or it wouldn't be much fun.

Edit: can't find a way to copy/paste the 234-character version to this browser, so I'm leaving the 235-character one.  Will fix this evening, when I get my hands on a real UTF8-aware clipboard. found a way.  Quasi-proof on ideone.