It appears to me that run() is being ran first and for a good amount of time before listen() is executed. How can I make this work?

The problem is a simple one. As each of your subroutines is running in a tight loop, the first one you set running will have looped many times before the second one gets started a split second later.

The fix is to slow those loops down. In the following I've added the subroutine pause() which is called from within both threads and causes them to only loop once every 1/10th of a second:

#!/usr/bin/perl

use threads;
use threads::shared;

sub pause {
    my $delay = shift;
    select '','','', $delay;
}

my ($stop) : shared; $stop = 0;

my $running_t = threads->new(\&run, 2);
my $listening_t = threads->new(\&listen, 1);

sub listen {
   my $cd = 10;
   while ($cd > 0) {
       print "waiting ... $cd\n";
       pause( 0.1 );
       $cd--;
   }
   print "SIGNAL HEARD! STOP RUN()\n";
   $stop = 1;

}

sub run {
    while(!$stop) {
        print "still running...\n";
        pause( 0.1 );
    }
    print "SIGNAL HEARD! STOPPING"
}

my @running_ret = $running_t->join;
my @listening_ret = $listening_t->join;

print "listen: @listening_ret\n";
print "run: @running_ret\n";
[download]

Now the output shows that they do indeed run concurrently:

C:\test>junk79
still running...
waiting ... 10
still running...
waiting ... 9
still running...
waiting ... 8
still running...
waiting ... 7
still running...
waiting ... 6
still running...
waiting ... 5
still running...
waiting ... 4
still running...
waiting ... 3
still running...
waiting ... 2
still running...
waiting ... 1
still running...
SIGNAL HEARD! STOP RUN()
SIGNAL HEARD! STOPPINGlisten: 1
run: 1
[download]

Play with the pause values (0.1) and see how different values produce different effects.