There are many programs like that, also depending on what platform you have, you can get different software.
Stuff you'll want would be something like Cakewalk Sonar (PC/MAC), eMagic Logic 5.5 (5.0 Final was for the PC, the rest are for MAC), Fruity Loops (forgot to state that in previous post), and I believe Cubase SX also lets you import VSTs and place notes on a staff. I'm not too sure, I've just used that to record lyrics.
The program that'll probably be best for you would be Propellerhead's "Reason 2.5"(PC/MAC). 2.5 just came out and it's suppose to be extremely uber. This is the program that got me into creating music actually, and it comes with an assload of samples (I believe the official version is about 3 discs long). There's no staff, but going into edit more, there's a Piano Roll (a visual of a piano that allows you to edit and place your notes on beat, in key, etc.). Reason is quite powerful when it comes to setting up mixing racks (press TAB and you get to view all the wires in the back...oooo...snazzy

). As for advanced music features, 2.5 allows the ability to add Ritards! WOO! finally! (previously unavailable), and key and time signature changes.
Once you really get into it, get another program that's more advanced, like eMagic Logic. It's most excellent and comes with a lot of features (and is VST compatable

).
Now, VSTs are interesting things that you should really get to know about. They're the wave of the future when it comes to music creation. VSTs and Virtual Effects were created by Steinburg originally, but there have been SDK releases, and people have been making their own. VSTs are basically your virtual instruments (Native Instruments makes THE BEST). People make them independently and share them across the internet, or they sell them. Which is legal :p. The most powerful VSTs out there are Reaktor 3 (which is a program that acts as a VST) and Absynth (which is primarily for synths). You can actually make your own instruments in these two programs, and import them into VST compatable trackers or mixers. It's good stuff...now if I can only remember what VST stood for, I'd be set *L*
All in all, Reason 2.5 is most definitely the program you want. It's not VST compatable, but it's a start.
I use Renoise 1.3, Reaktor 3, Absynth, and some VSTs. And trackers are pretty hard to get used to (things like Impulse Tracker, Fast Tracker, Mod Tracker, etc.) It's like programming a song.
Anyway, I hope this helped :p ja!