There are lots of things you can do. But first you need to understand what publicity is. A publicist takes information (in this case, most likely, information about a book release), and targets the audience best fit to receive that information. Down to its basics, it's a simple concept.
So take a few minutes and think: Who is the audience for my book? Don't limit yourself to expansive groups. Be as specific as possible. If your book is YA, then teens are obviously a good choice. But maybe your book is a YA mystery. So what kind of teen likes mysteries? Research is your best friend.
Sometimes you can directly target your consumer (high schools, DARE groups, mock trial groups), or sometimes you need to go through someone else to get to them: journalists, the high school paper, radio interviews, book signings, even parents. Local journalists love a good human interest story. Don't forget to pitch them--but this kind of story is more about you and your success than the book.
On the Internet, you can blog, you can Twitter, you can Facebook, you can visit other forums (just don't be spammy).
When you pitch, make sure you understand what it means to be newsworthy. Google this term. You'll find several different categories of newsworthiness--timeliness, human interest, proximity, etc.--and make your pitch fit into those categories. Half the time the focus WILL NOT be your book. In New York City, two romance authors set up a book signing on Valentine's Day. They turned the signing into a party, an alternate event for single women on Valentine's Day. The press they got mentioned the books, of course, but they got press because the event was timely with the holiday. Not timely because of the book.
There's a reason Harry Potter sold millions of books in its first hour of release--the marketers gave people incentive to go out and buy it at a certain time. They gave people a party. (And they gave bookstores incentive to host the parties.)
You have to give the journalist a story, don't expect them to come up with one. So first you have to understand what kind of story the journalist is looking for. Again, research research and research.
Best thing to do is think outside the box. Be creative. Take time with your book and really think about all the different angles you have in your story and who might be interested in them. Think about the timing of your release--any holidays or other interesting tie-ins? When it comes to the Internet, stay constant with your blog or Twitter updates and give people reasons to return--interesting content, contests, etc.