NOTE: update above on 12/10
I realize that most people won't read this, but I figure anyone who feels strongly enough to put their name on a petition might be interested enough in the issue to read a few more thoughts. I even tried to make them as entertaining as the story.
First of all, I agree with everything Jill has said here (except the stuff about Macy's--what a crap hole that place is, eh?) Like her I sympathize with this story, but there is more a vague whiff of racism and xenophobia about the whole thing. Which is understandable. I teach a class on Globalization and the section on migration is by far one of the most controversial. But in reading this story, I can't help but wonder how this old lady in line behind the "illegal" knew that this immigrant was illegal? I mean, did she ask her for her papers to verify if her ire was correctly placed or did she just assume that, because these folks have a different color of skin or have a different odor or way of dress that they were "illegal" immigrants. Could they not have been legal, in the country working on a visa or green card or naturalized citizens? I'm sure she has a lot of reasons to assume they are illegal, but let's just be clear, she's just assuming it.
So let's assume that all these wealthy immigrants are able to shop at fancy stores like Macy's. It would actually be a twisted sort of justice since, depending on the country they're from, they likely have relatives, friends or at the very least fellow (former) citizens who have gotten paid next to nothing to sew those clothes--which, incidentally, is why Macy's can afford to have those sales. Retail clothing stores like Macy's and JC Penny are the main reason all of our clothing production has shifted south of the border. They lobbied congress--against domestic US *AND* domestic Mexican clothing manufacturers--to be given all sorts of trade benefits in the NAFTA and CBI policies in the 1990s and then demanded that the clothing be so cheap to make (i.e. the people who made it be paid so little and worked so hard) that they wouldn't take a hit when they drop the price on that beautiful sweater you want. So if, by chance, someone made it up here from down there and they can afford the sweater, at least someone is getting ahead.
I'll address this hypothetical "illegal" alien at the supermarket by also speaking to the claim that there was a bill to give "illegal" aliens Social Security benefits they didn't pay for. Again, assuming this alien is illegal, meeting her in a supermarket--especially a new supermarket--would be an especially significant encounter--exactly in relation to the proposed SS benefit.
In 1996 Congress passed a comprehensive immigration law that some thought was tougher than any passed up to that point. For the most part it militarized the border beyond anything previously and made it tougher for immigrants to get into the country via the mythical nighttime border crossing (most of the people in the country--and in any western country--illegally simply overstay their visas, i.e. they get here legally, get work and then simply can't afford to take the time off of work to go through the increasingly arduous process of renewing their visa). On the flip side, this bill did fail to close the border across southern Arizona because they didn't think anyone would dare try making it across the Sonora desert into the US because the harsh conditions would likely kill them along the way. It didn' t stop all the immigration (see note above about visas) illegal or otherwise, but it did manage to create a growth industry for Mexican border coyotes (smugglers) who claimed to be able to help the less connected immigrants who couldn't get visas avoid the fate of the more than 1,000 immigrants who died in the desert from thirst and exhaustion.
But enough about dead Mexicans: back to the important issue of social security. Oh wait I forgot, that bill I was talking about above, it had this one provision that wasn't for the immigrants really, but for the IRS and employers who rely on (illegal) immigrant labor. It established what's called the Individual Taxpayer Identification Number, or ITIN . This really doesn't do a whole lot for employers (though it helps them hire people without a valid SS#) and theoretically wouldn't help legal or illegal immigrants, except that it would allow them to pay taxes into the Social Security system and then get their tax refund (as all my international student friends--here legally--have to do for their stipend money), but technically they would never be eligible for the benefits they paid into. In other words, it was a way for illegals or other non-residents to pay taxes and still work here, legally or illegally, but would never let them get the benefits.
So why would they pay this money you ask? Well there are a lot of reasons  but in short there was some belief that there would be another opportunity for amnesty of non-residant immigrant workers and so immigrants were encouraged to pay into the system as a show of good faith that they were contributing. So they paid into the system. So much that one study of the Arizona economy found, just through tax contribution, not through our indirect bnefit from their cheap labor, Mexican immigrants contributed $318 million more than they received in any form of benefit.  The bill in question isn't asking whether they would ever get a credit for the benefits they paid in if they became citizens.
In other words, the bill wanted to make sure that they would get credit for none of the years they had worked and paid taxes because, although they were working and paying taxes, they were here illegally. I'm sure we can all understand that because the law always makes sense and we always follow it. In fact, we'd probably all agree to a law that said if you ever broke the law you'd be ineligible for some of yor social security benefits.
Oh right...the grocery store, the older lady, the immigrant...that older lady in the grocery store might be getting stiffed by this immigrant woman (though, again, even if she's illegal, she's not receiving benefits yet even though it's possible she paid for them), but we would all be appalled at the price of a head of lettuce if you had to pay for the growers to hire legal workers and pay them a mimimum wage. Just about everything in the store--especially in the fresh foods aisles--would also apply as would the store itself if it was built in the last ten years: as anyone who drives near I-30 in downtown Fort Worth knows, the guys who are getting picked up to build stuff aren't exactly as white and whimpy as me.
None of this is to say that we don't have an immigration problem or that the government hasn't been colluding with business to make sure nothing really big changes . This is because if they actually enforced the xenophobic laws on the books, the contry would grind to a halt. On the other hand, if they made the kind of changes necessary, it would basically mean paying everyone a minimum wage--and then, likely, having to raise that wage again. While this would inarguably be a good thing, it would also make that head of lettuce or tomato about four times as much as it costs now, if not more.
Jill makes some very good points on the minimum wage, but I'd add that in this case illegal immigrants are, in part, one of the reasons that the minimum wage has been able to be held down. This is not just because is that there are still ways for employers to get around hiring legal workers--in fact, for the most part, the actual economic costs for comparable legal workers in terms of lost jobs aren't that significant. But the threat of illegal workers means there are pressures on the comparable force of workers to accept sub par wages. The focus on them by desparate Rebublican politicians mimics a long history of creating immigrant scares--first it was the Chinese...then the Germans...then the Irish...then the Polish...then the Italians...then the Japanese...now the rest of the people from Latin America, Africa and South Asia--always the claim is that, if you give labor rights to everyone, if you make it so that there isn't a legal underclass, then you might lose something: and besides aren't those immigrants dirty, scary, criminals, with loose morals, and big feet? You don't want them near your daughter do you? Better to deny yourself rights to a union or rights to a higher minimum wage: if you can't get it "they" can't get it. In fact, this is probably the biggest reason there wasn't a strong movement for socialism in the 19th century in America: "whites" refused to think of themselves as equal to the inferior races like African Americans and Chinese and the Irish. I have some nice articles about this, too, for anyone who's interested.
The tax cuts for the rich are an even bigger scandal because they are calculated efforts by people within the neo-conservative movement to create a fiscal crisis in the US so that the government will be forced into spending cuts and (more costly) privatization schemes. One of the promonent proponents of this line of policy--called "starve the beast" --is Grover Norquist who is famous for saying that he'd like to get the government down to the size where you could drown it in the bathtub . A few people wondered if he had a laugh about that when New Orleans was suffering from its own lack of government funds. 
Okay. I'll be in enough trouble as it is for writing this. I'll go to bed now.
1] http://www.irc-online.org/us-mex/borderlines/2001/bl79/bl79deaths.html this is an early article on the problem and here is an interview that mentions the 1000 deaths number--that was back in June of 2001--only halfway between when the border was beefed up and today.
it's also worth noting on this point that militarizing the border further, whatever it's effect on inflow of immigrants, significantly affected their outflow. A study by a sociologist named Douglas Massey who has been looking at this for close to twenty years found that, before the 1996 act, migrant workers were much more likely to stay for a couple of years, make some money and then go home; but militarizing the border made it much more likely that, if they were able to make it here, but unable to gain or maintain legal status--which often means hiring a lawyer to handle a bunch of crap paperwork--they were more likely to stay here, even if separated from their family because they weren't sure if they'd be able to return. THe only articles I have about these studies require access through my school library but if you're interested in them, I can send them around. For a brief synopsis of his work, here is a podcast of a NYC radio show that Doug Massey was on in April. In it he discusses how his research has worked and what it proves. His interview is in the second half of the show, probably around the 30:00 mark.
3] there are lots of stories like this one http://www.sptimes.com/2006/01/23/Northpinellas/Tax_IDs_give_illegals.shtml
4] "Based on the 2000 Census and the tax projections of the Mexicans in Arizona, the sales tax and federal income tax contributions from Mexican immigrants are approximately US$599 million for 2002. If we subtract the total burden costs of services for the Mexican immigrants of US$250 million and US$31 million of uncompensated health care costs of undocumented Mexicans, we still have fiscal surplus resources of US$318 million." http://www.ime.gob.mx/investigaciones/aportaciones/arizona.pdf
5] ONe article of many discussing how the Bush administration pulled the INS dog off of employers so they could get away with hiring more illiegals: in short "Between 1999 and 2003, work-site enforcement operations were scaled back 95 percent by the Immigration and Naturalization Service, which subsequently was merged into the Homeland Security Department. The number of employers prosecuted for unlawfully employing immigrants dropped from 182 in 1999 to four in 2003, and fines collected declined from $3.6 million to $212,000, according to federal statistics.http://www.washingtonpost.com/wp-dyn/content/article/2006/06/18/AR2006061800613_pf.html