Firstly, I agree with toolic above, that hashes are likely to be much better for what you are trying to do.

Second, have a look at splice for the splice syntax. Rather than using the name of the item you want to splice, you should provide the index, and number of items. Something like this:

#!/usr/bin/perl
use warnings;
use strict;

depo();

sub depo {
        my @storage = qw(knife wand bow);
        my @inventory = qw(axe sword shovel);
        my $num = 1;
        my $choice;
        my $item;

        sleep (1);
        print "Which item would you like to deposit?\n",
        "$num. Nevermind\n";
        foreach my $inv (map(ucfirst, @inventory)){
                $num++;
                print "$num. $inv\n";
                }
        $choice = lc(<STDIN>);
        chomp $choice;
        my $index = 'N';
        
        for (my $x = 0; $x <= $#inventory; $x+= 1)
                {
                        if ($inventory[$x] eq "$choice")
                                {
                                         $index = $x;
                                         $item = $inventory[$x]; 
                                }
                }
        
        if ($index eq 'N')
                {
                        print "$choice is not available.\n\n";
                        return;
                }
        $item = splice (@inventory, $index, 1);
        push(@storage,$item);
        print "You have stored a \"$item\".\n\n";
        print STDERR "STORAGE: @storage\nINVENTORY: @inventory\n\n";
}
[download]

I hope that helps a little.