You'll find the following handy:

print("\010"); # backspace        Moves cursor left one.
print("\r");   # carriage return. Moves cursor to start of line.
[download]

Specifically:

use strict;
use warnings;

use Time::HiRes qw( sleep );

my @sparkle = qw( \ | / - );
my $cur_sparkle = 0;

$| = 1; # autoflush

print(' ');

for (;;) {
   $cur_sparkle = ($cur_sparkle + 1) % @sparkle;
   print("\010$sparkle[$cur_sparkle]");

   # Do a work unit.
   sleep(0.250);
   last if not int(rand(50));
}

print("\010done.\n");   # or: print("\010 \010");
[download]

Update:
Replaced Timer::HiRes with Time::HiRes.
Replaced \08 with \010.
Added $| = 1;
Removed last | from @sparkle to smoothen the animation.