by Patricia Sellers

The best stories of personal success defy the odds and the career rulebooks.

Paula Deen takes the cake.

The silver-haired, Southern-cookin’ star of the Food Network, has sold more than 8 million books. She’s got licensing deals with Wal-Mart (WMT) and other major companies. She has a magazine, Cooking with Paula Deen. And at 62, she has more fans on Facebook than Bill Clinton. And more followers on Twitter than David Bowie, Carson Daly, Tavis Smiley, and country star Martina McBride.

No one–and least of all Deen herself–could have imagined her success today. I interviewed Deen on stage last week at a “Fortune Most Powerful Women Evening With…” dinner, one in a series of regional events to accompany Fortune’s annual Most Powerful Women Summit. This “Evening With…” was in Atlanta and drew top women execs from Atlanta-based Fortune 500 companies like Coca-Cola (KO), Delta Airlines (DAL), Home Depot (HD), and UPS (UPS).

Best that Deen, who lives in Savannah, tell you her life story. Watch the video below. See what a hoot she is. And hear an extraordinary rags-to-riches tale.

I’ll give you a quick flavor, so to speak. Married to an alcoholic, broke, and agoraphobic for many years, Deen broke out of her personal prison 20 years ago, at 42. She started a tiny catering business with her two sons, and then a restaurant–funded by her Aunt Peggy, now 80 and ever spry. Aunt Peggy and Michael Groover, Deen’s second husband whom she married five years ago, were also with us last week to hear Paula pass on her entrepreneurial advice.

“I am living proof, y’all, that the American dream is still much in existence,” she told me on stage. “I’ve proven, you don’t have to be 30 years old. I have proven, you don’t have to be a size six. And I have proven that you don’t have to have blond hair.”

Hear it straight from Paula Deen–and enjoy…

Carly Fiorina declared her candidacy for the U.S. Senate–in a bid to replace another well-known woman, incumbent California Democrat Barbara Boxer.

Fiorina, who was No. 1 on Fortune’s Most Powerful Women list for six years when she was CEO of Hewlett-Packard (HPQ), will be pounding the campaign trail simultaneously with another ex-No. 1 on our list: Meg Whitman. The former eBay (EBAY) CEO, who topped Fortune’s power list in 2004 and ‘05, is running for Governor.

Neither woman, both Republicans, will have an easy time in the left-leaning, financially crippled Golden State. Running on her “I’m a great manager” platform, Whitman has a decent shot at her party’s nomination. But she faces a fierce Democratic rival in Jerry Brown, California’s current Attorney General who once was Governor. Another Democratic rival, San Francisco Mayor Gavin Newsom, just dropped out. (For more, check out my recent cover story, “Can Meg Whitman Save California?“)

Fiorina, who yesterday revealed her plans in the Orange County Register, has a personality tailor-made for campaigning: She’s charismatic and commanding. Remember when she was waging that brutal proxy fight to buy Compaq in 2002? She played it like a political candidate–and she won.

But Fiorina, 55, who worked with Whitman on John McCain’s failed Presidential campaign, carries significant baggage into this latest race: She was fired by the H-P board in 2005–as much for her style of leadership as her disappointing execution.

Another battle lately has been a medical one. Fiorina was recently treated for breast cancer. In September, while undergoing daily treatments at Stanford Hospital, she spoke by video-conference, along with Elizabeth Edwards, to participants of the Fortune Most Powerful Women Summit. Here’s a clip:

Kudos to Fiorina for speaking out. The fact that she’s running for the U.S. Senate is a sign that her prognosis is good. And she’s as tenacious as ever.

by Patricia Sellers

Photo courtesy of Avon

Liz Smith, who was on track to succeed Andrea Jung as CEO of Avon Products (AVP), is moving to a new company and a new industry. Again.

The onetime star exec at Kraft (KFT), who made an unlikely leap from food to cosmetics in 2004, is the newly named chief executive of OSI, a chain of casual-dining eateries.

“What?!!” is a question that Smith admits she’s been asked often throughout her career. She says she follows her own guideline: “Be open to opportunity.”

There’s plenty of opportunity–and risk–at OSI, which you may not have heard of but is a giant in the casual-dining category. With 2008 revenues of $4 billion, OSI operates chains such as Outback Steakhouse, Carrabba’s Italian Grill, Bonefish Grill, Roy’s, and Fleming’s Prime Steakhouse and Wine Bar. Good brands, as restaurant brands go–and as Bain Capital and Catterton Partners thought when they acquired the company for $3.2 billion in 2007. But the global recession brutalized the business, which operates across the U.S. and in 20 other countries. OSI lost $739.4 million last year, and it’s been suffering serious declines in same-store sales.

Which may be ideal for Smith, since she adores companies that are ripe for overhaul. “It’s really always been in my DNA,” she told my colleague Jessica Shambora in September, on the day she announced her departure from Avon.

Smith’s exit from Avon shocked many people, since she was crucial to the cosmetic giant’s turnaround, well-liked across the company, and widely viewed as Jung’s eventual successor. But “eventual” was looking to be too long from now. While Smith, who is No. 29 on Fortune’s Most Powerful Women in Business list, is just 46 years old and has plenty of runway ahead, she lost patience. That’s understandable since Jung, who was named Avon’s CEO at age 41 a decade ago, has no plans to retire.

So now, Smith–who began her career at Morgan Stanley (MS) and then, as a Stanford MBA student, “wanted to start the next Microsoft or H-P”–is off in yet another new direction. Geographically, this time it is Manhattan to Tampa, Florida, where OSI is based. Smith plans to commute initially and then relocate with her husband and two young sons.

And though retail isn’t entirely new to Smith–she’s on the board of Staples (SPLS)–she’ll be testing herself against her own measure of leadership. “Nothing is more important than a nimble, agile leader who is comfortable with ambiguity,” she told me a few months ago.

“We have to be comfortable figuring it out as we go along,” Smith added. Definitely, she’s living her philosophy.

by Patricia Sellers

Greetings from Atlanta. I’m here for Fortune’s “Most Powerful Women Evening With…” Atlanta is tonight’s stop in a series of regional dinners that we’re hosting annually in addition to the main event, the Most Powerful Women Summit. I’ll be interviewing Food Network star Paula Deen, the silver-haired, Southern-cookin’ entrepreneur and star of the Food Network. Also with us: the top women execs at companies like Coca-Cola (KO), Home Depot (HD), Delta Airlines, (DAL), UPS (UPS), and Turner Broadcasting, which is part of Fortune’s parent, Time Warner (TWX).

It’s fascinating to be here since I grew up, career-wise, learning about business from two Atlanta-based Fortune 500 giants: Home Depot, back in the ’80s and ’90s when co-founders Bernie Marcus and Arthur Blank were running the place, and Coca-Cola, when the late CEO Roberto Goizueta built Coke to be Fortune’s No. 1 Most Admired Company.

Isn’t it interesting that a false sense of invincibility and arrogance eventually poisoned both corporate cultures? Coke and Home Depot fell off the tracks, struggled through lines of wrong CEOs, and had their comeuppance. Only after painful cost-cutting and serious strategic rethinking did they begin to return to prominence.

I spent this morning at Coke with some folks who’ve been key to its recovery. One is SVP Wendy Clark, a hotshot marketer who joined Coke last year from AT&T (ATT) and this year made Fortune’s “Women to Watch” list in the Most Powerful Women issue. I also caught up with Clyde Tuggle, Coke’s global communications chief whom I’ve known since the ’80s, the Goizueta days.

Talking with Tuggle reminded me how radically marketing has changed. In May, he told me, he asked Coke’s social media experts to come up with “a big idea” that would be unique and turn consumers into brand marketers–what smart brand-owners must do today. The team delivered an idea called Expedition 206. It’s an online contest in which consumers vote, via Facebook and Twitter and other social networks, to elect a trio who will visit every country in the world where Coke sells its products. (Yes, Coke is in 206 countries.). Consumers have selected three finalist trios–who, if you look at the Expedition 206 site, you’ll see are from all around the world, literally. The winner will emerge in two weeks. Starting January 1, that trio will spend 365 days globetrotting “on a mission, quite simply, to find happiness,” as Tuggle puts it.

It’s a gimmick, but maybe a clever one in this new era when consumers, not companies, control public image.  “We have to move into a space where we let go,” as Tuggle says. “The world gets to experience the brand through the eyes of the consumer, not the company.”

Indeed, the consumer is now the chief marketing and communication officer.

by Leigh Gallagher, Fortune Senior Editor

Why do women lag men on Fortune’s 40 Under 40 list of the most influential rising stars in business? Yesterday we delved into this question and shared insights from two experts: Facebook COO Sheryl Sandberg and McKinsey director Joanna Barsh. Sandberg’s and Barsh’s opinions provoked some interesting comments, including one from David in New York City, who declared that women “have all the brains and tools but lack the drive,” followed by Michelle in Toronto, who argued that women “are not nurtured at a young age to be entrepreneurial or business-minded.”

A few more insights from Barsh, who carefully explored this territory to research her new book, How Remarkable Women Lead. Barsh believes that women are more interested than men in finding meaning in their careers than, say, wealth or power. We buy into that–and we’ve been struck over the years by how many stars of Fortune’s Most Powerful Women list, such as former Procter & Gamble (PG) president Susan Arnold, have thrown in the towel for a break or a better life outside of business.

But Barsh also thinks that women may be wired with a lower tolerance for risk, and therefore are less likely to risk it all to try to create the next, say, Google (GOOG) or Twitter or Ford (F) or Coca-Cola (KO). “Women are so busy pleasing everyone that they’re in the get-an-A-mode,” she says. “That causes you not to take risk.”

Such theorizing gets really interesting when you delve into the question of why women don’t take as big risks as men do. Theories abound, but one of Barsh’s favorites comes from Florida State University social psychologist Roy Baumeister, who focuses on the theory that in ancient times, many more women reproduced than men. Baumeister suggests that the ratio could be as much as two times (say, 80% of women and only 40% of men were fortunate enough to have progeny).

Starting with the premise that our biological necessity is to reproduce, a woman’s job was to protect her eggs, whereas men’s job was to risk it all to win a mate. As Baumeister theorizes, over time that risk-taking requirement became hard-wired for men at the same time the nurturing instinct wired itself in women.

The fact is, we are descendants of women who played it safe–and men who, to win a woman’s hand (and the chance to procreate), had to compete. “In order to fulfill their biological goal, men had to take huge risk,” Barsh says. “They had to go to war and come back with money.” Not all men did, which could explain why fewer of them reproduced than the women, who were the ones being pursued.

Such anomalies of risk-taking aside, men have greater variability in general, Barsh notes. This variability enhances the chances that more men than women hit the heights in the corporate world; meanwhile, more men than women also fall in the gutter. “If you take the smartest people and the dumbest people, there are more men in both buckets,” Barsh explains, adding, “Look at people in jail. There are mostly men in that group, too.”

Come to think of it, a few of those jailbirds were once in business, and probably took risk too far.

Just look at Fortune’s annual Most Powerful Women list to see the strides of women in business: Today an executive, to make the cut, generally needs to oversee some $6 billion in revenue, vs. about $1 billion 11 years ago when we launched the list. Still, the debate rages about why women aren’t moving up the ranks faster. My theory: Women tend to view power horizontally and live their lives in chapters–and so, even if all the glass ceilings across the world shatter, women will not catch up with men in terms of power. Still, we were surprised to discover how few women made Fortune’s just-released 40 Under 40 list of the most influential young people in business. So we asked Senior Editor Leigh Gallagher, who commandeered the project, to share her insights–which are fresh, smart and eye-opening. Here’s Leigh on the dearth of female rising stars:

In putting together Fortune’s 2009 list of the 40 Under 40, here’s the trend that stood out: Men outnumber women in our rankings by a ratio of 7 to 1.

Yes, there are only five women on the list. We can express indignation at this because it wasn’t our intention or our choice. In fact, we shook the trees pretty hard to make sure we weren’t missing anyone.

Make no mistake: The women who made our list–financial analyst Meredith Whitney, Google VP Marissa Mayer, Ning CEO Gina Bianchini, CNBC (GE) anchor Erin Burnett and Coca-Cola (KO) marketing’s Wendy Clark–have all zoomed past men in their respective fields. But there are no women listed who, say, founded a Google (GOOG) or a Facebook or a Twitter. None who are self-made hedge fund billionaires. None who made it to the top 10. So, while the accomplishments of those five women are tremendously impressive, they still, for the most part, trail those of most of the men on our list.

What gives? I asked Sheryl Sandberg, COO of Facebook and one of the most prominent leaders in Silicon Valley, to weigh in. She cited some interesting numbers: Just 15 of Fortune 500 CEOs are women. Yet at the college level, more women are getting degrees than men–and even some professional schools are graduating more women than men. “So the question is,” Sandberg says, “what happens between leaving school and age 40 to make this list predominantly male?”

Sandberg (who, by the way, would have made the 40 Under 40 list if she hadn’t turned 40 this year) says she suspects that “disequilibrium of household responsibilities,” as she calls it, is a key reason women slip behind. Even when both men and women in a household work fulltime, she notes, studies have shown that women do the majority of the childcare and housework. Perhaps that’s not so surprising, but Sandberg’s point is that advancements on the domestic front seriously lag the gains women have made in the workforce.

“Over the past 40 years, we have made more progress in the workplace than in the home,” Sandberg says. “I believe the No. 1 thing we could do to change the numbers in the professional world is to find a way to balance responsibilities in the home.”

McKinsey director Joanna Barsh, who pioneered the firm’s Centered Leadership Project to help develop women leaders, thinks along the same lines. She points to the practical limitations that child rearing can put on women’s careers. “Not everybody slows down,” Barsh says. “But an awful lot of women choose to slow down and enjoy those years.” And for many women, she notes, the slowdown comes at the precise time when career opportunities tend to surge. “Your hormones are causing you to want to take care of everyone in your family at the very moment when you’re building your goal lines.”

Many women “zig and zag” rather than pursue one goal in a straight line, as most men are programmed to do. Women can still accomplish a great deal career-wise, but it might happen when they’re well past 40. Barsh’s idea for fixing the gender imbalance on the 40 Under 40 list? “Give women a ten-year handicap!”

Well, we can’t do that. But we can hope to see more women in the 40 Under 40 rankings in coming years. To be sure, half the people on our “Ones to Watch” list of fast risers are women. I asked Sandberg how long she thinks it will be until a woman co-founds a $100 billion company. Her answer: “Who says she hasn’t already?” She makes a good point. And we’ll be watching.

P.S. Tune into Postcards tomorrow for further discussion. And for more of Sandberg’s insights about navigating a successful career, read her first-personer, “Don’t Leave Before You Leave.”

“You need to build your career not as a ladder, but as a pyramid,” Yahoo (YHOO) CEO Carol Bartz said in the New York Times yesterday. I wholeheartedly agree: In today’s ever more complex world, you need to build a broad experience base–with peripheral vision and a willingness to make lateral moves. If you’ve been reading Postcards, you know that my favorite image is a jungle gym. That’s kind of like Bartz’s pyramid.

You can read more of Bartz’s career advice in her first-personer, “Just Deal with it.” But it was at last month’s Fortune Most Powerful Women Summit that she spoke about public-company board work as essential to career-building and vented about the “nonsense” of CEOs prohibiting high-potential execs from serving on other companies’ boards. The Yahoo chief is colorful, as usual, as she describes her first board meeting as the new CEO of Autodesk (ADSK) in 1992, the day after she was diagnosed with breast cancer. “I didn’t even know what a friggin’ board was,” she says:

During her 14 years running Autodesk, pre-Yahoo, Bartz was on the boards of Cisco (CSCO), Intel (INTC), NetApp (NTAP) and BEA Systems–until it was acquired by Oracle (ORCL). That’s a heavy load that I’d say paid off in prepping her for Yahoo, where she arrived in January. My Fortune colleague Adam Lashinsky and I have sparred on the value of such multiple directorships. We’ll see tomorrow how well Bartz is doing. She’s due to report Yahoo’s quarterly earnings.

There comes a fork in every career. Should I do this or do that?

Charting a successful career was the topic on Tuesday at Wal-Mart (WMT), where the company’s female officers staged a “Fortune Most Powerful Women” event and I interviewed two stars of the 2009 MPWomen rankings: Wal-Mart EVP of People Susan Chambers and Xerox (XRX) CEO Ursula Burns.

Their bios tell the paths they chose. More inspiring and instructive, as they revealed on Tuesday, are the career paths they decided not to take.

Chambers, who joined Wal-Mart from Hallmark a decade ago, once dreamed of being a professional opera singer. Her mezzo-soprano might have been, but she didn’t love the idea of traipsing around the world as artists must do. “It’s still in my heart,” said Chambers, who now plays piano and sings–at home and at church–to lessen the stress of overseeing the largest private-sector workforce on earth. “Make sure you spend some percentage of time doing something that brings you joy,” she advised.

Burns told a story that few people know–how in 2001, she almost left Xerox.

Having joined Xerox as an intern in 1980, Burns by then had ascended to SVP in charge of manufacturing and supply-chain operations. a stellar rise, but Xerox was teetering–facing potential bankruptcy–and its CEO, a former IBMer (IBM) named Rick Thoman, had lost the faith of investors and management.

Burns was outta there–or so she thought. She had lined up a job at a healthy, younger company and was about to move to Texas with her husband and two children when she got an unexpected call from a Xerox board member.

This director said to her: “If your spouse was old, but now they are sick, would you stay and care of him?”

Yes, of course, Burns replied.

“If you and your spouse both made it through to a long-term relationship, but now a young, ‘pretty’ suitor came along, would you stay in the relationship you’ve invested in–or leave for something new and unknown?”

Stay–absolutely, Burns told the director.

It was at that moment, Burns said, that she realized she was key to saving Xerox. And when she learned that the board was going to name Anne Mulcahy, another lifer who embraced the need for radical change, as the new CEO, Burns ditched her departure plan.

So, what was that healthy, younger company that almost lured Burns away? “Dell,” she told the Wal-Mart gathering.

And who was that Xerox director who persuaded her to stay? “Vernon Jordan,” said Burns, referring to the well-known Lazard (LAZ) lawyer who, besides serving on Xerox’s board, advises American Express (AXP), where Burns is a director. By sticking it out, she eventually made history: The Mulcahy-Burns succession, in July, was the first-ever woman-to-woman CEO handoff in the Fortune 500.

P.S. For more Wal-Mart wisdom, read my Wednesday post, “A visit to Wal-Mart’s home.”

by Patricia Sellers

Maybe it’s a sign of recovery in the financial services industry: Wall Street’s two most renowned women dropouts have settled on what to do next. Yesterday on Postcards, you read Sallie Krawcheck’s bizarre tale of her bumpy road on the way to Bank of America (BAC). Today, news broke that former Morgan Stanley (MS) co-president Zoe Cruz is starting a hedge fund.

Cruz, who spent her entire career at Morgan Stanley (starting as a summer associate in 1981), got fired by CEO John Mack almost two years ago, taking the hit for the firm’s huge trading losses. This morning, the Wall Street Journal reported that she has begun recruiting employees for her new firm, to be called Voras Capital Management. The name refers to a mountainous region near where Cruz grew up in Greece.

Famouly press-shy, Cruz declined to talk about her plans. In fact, she has not spoken publicly for many years–except for one interview that she did with me in September 2007, shortly before her ouster at Morgan Stanley. Cruz told me then that she never planned her career. “When you don’t plan, things are easier,” she said. She was interested in one thing, she explained: “Leading an organization to be No. 1.”

Now hoping to launch her hedge fund with at least $200 million, Cruz is starting from scratch for the first time in her life. That name, Voras, suggests where she hopes her business will go: “Voras” is Greek for “north.”

“The age of thrift is here. You have to do innovation at both ends–premium innovation and innovation for the value consumer.”

– PepsiCo (PEP) chairman and CEO Indra Nooyi in a recent Q&A with Pattie Sellers. No. 1 on Fortune’s 2009 Most Powerful Women in Business list (for the fourth year in a row) Nooyi today delivered another quarter of solid earnings. PepsiCo beat analyst expectations with net income of  $1.72 billion, up 9% over last year.

Nooyi is relentless in reinventing a company that many others might have thought didn’t need reinventing. Investing in healthier products, reorganizing her core team, spending billions to acquire Pepsi’s two largest bottlers…the list of changes go on and on. “Any capital we invested in the company has to be rethought,” Nooyi said in the interview, noting, “The bottom line is: Through this downturn, you have to increase your investment, not cut back.” She added, “Now is a wonderful time to look for disruptive models.”

Click here for a series of video clips from Pattie’s interview with Nooyi. –Jessica Shambora