How do I do this in 11.04? Open Terminal from "Applications->Accessories->Terminal"

There must be an icon to open it to the left Unity toolbar (with a little screen black box)

The easiest way to open the Terminal is to use the 'search' function on the dash.
Or you can click on the 'More Apps' button, click on the 'See more results' by the installed section, and find it in that jumble of applications.
A third way, available after you click on the 'More Apps' button, you can go to the search bar, and see that the far right end of it says 'All Applications' You can click on that, and you'll see the full list, then you can go Accessories > Terminal after that.

So the ways that I could find are
Dash > Search for Terminal
Dash > More Apps > 'See More Results' > Terminal
Dash > More Apps > Accessories > Terminal

When you find it, you can drag it over to the Unity Launcher, to make things easier, if you use it often.

Though... I agree, it shouldn't take so much just to find the one application. It would be nice if I could go Dash > Accessories > Terminal, possibly in the old menu format, so I wouldn't have to Double-Click so much.

Actually, I think the easiest way to run the Terminal is the same as it used to be with a Classic Desktop:

Ctrl+Alt+T