I've found myself answering this question repeatedly in different places, so that must mean it needs a proper treatment.
Here are the four major (and two minor) markets of readers for which manga are written:
And here are some of the genres:
Slice of Life
Sword and Sandals (my term, from hollywood movie genres. Maybe it should be 'katana and geta?')
Note that these two groups don't look anything alike. It behooves you not to confuse them.
OK, so I've thrown out these words, now I'll define them. First some background: The manga market in Japan is huge. Everybody in Japan reads manga of some kind or other, even if it's only Azumanga Daioh (vaguely analogous to Peanuts in its heyday) or Tonari no Yamada-kun (which is kind of the Japanese Blondie). Because there's so much money to be made in manga, there are a lot of manga out there, and it's a big business. Manga are published in all kinds of magazines, from newspapery rags all the way up to slick, fat monthlies like Kodansha's Afternoon.
Because so many manga are published, categories (based upon the demographics that read a particular magazine - their markets, if you will) have arisen. There are four big markets defined (five if we count small children):
Shounen Means "young men," refers to male readers between about 10 and 17 years old.
Shoujo Means "young women," refers to girls the same age as shounen above
Seinen Means "mature men," refers to readers 18+.
Josei Means "mature women," as above.
There are also some marginalized markets that nonetheless get magazines and (lots of) doujinshi printings:
Shounen-ai is male-male romance stories (think shoujo romance with all guys)
Yaoi = male homosexual stories
Yuri = female homosexual stories
Differences: If it's meant for underage readers, it'll be short on nudity, short on adult themes, and (if you're looking at the Japanese original) there will be teeny-tiny 'helper hiragana' beside the kanji (Chinese characters) that much of Japanese writing uses, because school kids haven't really learned all the standard kanji until they hit age 15 or so.
I include shounen-ai, yaoi and yuri under markets and not genres because they seem to be in their own 'mauve ghetto' just as in the west, are written for distinct readerships, and don't much cross over into the mainstream, although the lines are definitely starting to blur, especially with more anime being derived from (more thematically complex) light novels instead of manga. Simoun and Strawberry Panic are two examples of non-marginal anime that definitely have some yuri going on in them. Shounen-ai and Yaoi, by comparison, still seem to be relatively marginalized except as a source of humor.
How to tell what it is if you don't already know:
Shounen: usually has adolescent male hero, friendly, possibly romantic but not sexual opposite-sex relationships, mild fan-service, action but not gore, and plots that would appeal to a boy in junior high - lots of aliens, espers, time travelers, strange monsters, and saving the world, or at least winning the big game and getting noticed by the desired girl because of it. Girls (and usually adult women) will be unusually busty for their age and (these days) beyond the realm of anatomical possibility. There are also often female character archetypes like meganekko (glasses girl), klutzy girl, brash girl (uses boku), etc. Bishounen (pretty-boy) character designs never occur in shounen or seinen manga except as a source of humor (cf the "Seiji in Kouta-Vision" scene in Midori no Hibi).
Examples: Naruto, Midori no Hibi, Great Teacher Onizuka, Eyeshield 21, Ruroni Kenshin.
Shoujo: Hearts and flowers. Adolescent female heroine. Heroine often chibi (unusually small even for a Japanese schoolgirl) Real, hardcore shoujo usually involves lots of romantic yearning and melodramatic situations (dead/absent parents, etc.) Nothing even vaguely resembling fanservice; girls are drawn as flat-chested as real Japanese girls are. If you see a girl in a swimsuit, it's arranged like a fashion show, rather than eye candy. Males are often drawn unrealistically 'pretty' (bishounen, as in Fruits Basket). Heroine is usually striving for some unattainable standard of goodness/moral perfection often in hopes that if she tries just a little harder Mr. Right will notice her/want to be romantically involved with her, or she'll fix everybody's emotional problems, or some combination of the two. Often spends ink on the relationships between heroine and her posse of female friends. Even when Shoujo wanders into more adult themes, lots has to happen offstage to keep things G rated, so we tend to hear about violence and sex rather than see them.
Examples: Kareshi Kanojo no Jijou, Fruits Basket, Bokura ga Ita, Revolutionary Girl Utena, Alice 19th, Fushigi Yuugi, Bishoujo Senshi Sailor Moon, Jigoku Shoujo
Seinen: Hard to define because so broad a classification. Some seinen manga are basically shounen manga with more violence/blood and gore/heavy fanservice/sex. These are meant to appeal to high-school and older males who want more of that Drifting Classroom feeling in an R-rated package.
Other seinen manga are basically adult light novels with pictures. The most thematically complex seinen manga fall into this category: things like Ai-Ren. Still others are simple escapism (usually in the slice-of-life or school life genres), because being a salaryman in Japan is hard and exhausting, and there's a steady market for simple, comforting stories that soothe. Most of the genres available in shounen are also done in seinen manga, although some are much rarer - sports manga, for instance.
By comparison, comedy romance and romance manga seem to be commoner as seinen manga than shounen manga (though I suspect they draw a certain amount of older nominally-shounen readers). Likewise, the slice-of-life category doesn't much exist as shounen (with the exception of general-interest manga like Today in Class 5-2 and Azumanga Daioh).
Real hardcore slice-of-life like Yokohama Kaidashi Kikou seems to be a uniquely seinen thing. Harem romance comedies tend to have a different spin, with the male lead having sexual relationships with more than one of his female companions, as in Honeymoon Salad. Generally, if it's R rated for sex, or sex forms a significant plot element, or there's gory violence, or lots of bare busts, it's probably seinen. If it is strangely plot-free and is slice-of-life, it's probably seinen.
The last seinen category that comes to mind is wistful nostalgia. You have something like a magical girl story but with deliberate anachronistic touches which is designed to appeal to older family men who want a simple story with happy endings that reminds them of the notionally simpler and happier days of their youth. Things like Kamichu! and Binchou-tan fall in this category.
Examples of seinen: Honeymoon Salad, Futari Ecchi, Vagabond, Ghost in the Shell, Kamichu!, Onegai Teacher, Yokohama Kaidashi Kikou.
Josei: Shoujo aged up for women. Most often grown-up shoujo stories (romances like Honey and Clover) along with workaday stories like Hataraki Man. You can spot a josei story pretty easily - there'll usually be at least one flat-chested chibi adult female in the female posse, and these never occur in seinen or shounen stories. Likewise, the shoujo drawing convention of creepy-big round eyes seems to show up in Josei as well. Again, the material looks superficially like what you find in shoujo, but with more adult plot elements and themes. If it's older-themed material, but the women are mostly flat-chested with big round eyes, it's josei. As in shoujo, the focus is on interpersonal dynamics and relationships rather than saving the world, blowing stuff up, or winning the big game.
Examples: Hataraki Man, Honey and Clover, Nodame Cantabile, Gokusen
That said, there is obviously a lot of crossover between josei and seinen. Yokohama Kaidashi Kikou could easily be called josei, except that it's published in the largest seinen monthly, and the character designs don't quite fit the standard shoujo/josei model. I think it's pretty obvious that there's a lot of female readership of Afternoon, so the mangaka deliberately avoided alienating the woman reader with a more male-oriented set of character designs. Likewise Hataraki Man, which has a busty female lead. It's josei, but there's supposed to be some crossover appeal to the seinen reader as well. Similarly, Ayu in Honey and Clover has more eye-candy value than she needs to in the shoujo/josei mold. Bishounen designs seem not to occur as often in josei, probably because of the desired market crossover.
Shounen-ai: boys love boys, but don't actually do much about it. Tends to use a lot of bishounen character designs, and has its own iconography involving guys lying on beds of roses, etc.
Yaoi: boys (and men) love boys (and men). See above about shounen-ai, but add in more (ahem) mature content. My understanding is that the biggest consumers (and producers) of shounen-ai and yaoi material in Japan are women.
Yuri: girls/women loving girls/women. Tends to look like shoujo romances, but with all females.
Examples: I don't read this stuff, so know it more by joking mention in mainstream material than anything else. I could go to mangaupdates and look stuff up, but then so can you, and I'm not interested.
I won't spend a lot of time on genres - these should be pretty self-explanatory once you've actually read a few manga. One note worth mentioning: A magical girl story is about a girl (typically under age 15) who has some supernatural power and uses it do to good. A magical girlfriend story is a romance about a guy who gets a girlfriend via some unlikely/impossible/magical means. The girlfriend frequently has magical qualities or abilities. Probably the perfect example is Aa Megama-sami/Ah! My Goddess.
Genres mix and match - you can have a science fiction magical girlfriend romance (Chobits), or a fantasy magical girlfriend romance (Ah My Goddess). Likewise, nearly anything can be highly plotted or not. If it's not highly plotted, it probably qualfies as slice-of-life regardless of its other attributes. So yes, you could have a slice-of-life historical adventure romance-comedy. I can't name one like that, but there are some that need that many compounds to be adequately explained.