Welcome to the Woodworking Stack-Exchange!
Just glue them together - would not be strong..
It would be plenty strong. As @Pete mentioned in his answer the glue joint is stronger than the wood it's holding together. That is,
- If you can apply enough clamp pressure
- Have smooth surfaces before gluing them together. A jointer, planes or just sanding helps in that regard.
- The type of wood plays a role as well, though if you only use 2x4s from the hardware store like fir, spruce or something alike you should be good.
As you mentioned that this is your first woodworking project, my guess is, you don't have a jointer or other fancy power tools that would ease up the creation. Hand-planes are not too expensive though and you can achieve satisfactory results with them (and a little patience, practice and perseverance) as well. If those aren't an option either, make sure the surfaces that are glued together are as straight and clean as possible by sanding them.
Cut a rabbet vertically and slide them in - rabbet along the grain may not be strong as well.
I think the rabbet would give the joint even more strength, as well as help you align it and avoid slipping when you glue it up. Gluing long-grain is what you actually want to do as it is considered a strong bond when gluing. For more details on different grains and their strength in glue joints please refer to this question.
Drill 5/8" holes in them and use circular hardwood dowels
If you do this in addition to gluing, that would provide a pretty strong joint that wouldn't come apart any time soon, but in my opinion a severe overkill. Also worth mentioning with this approach is that it can either be optically disturbing, or a really beautiful addition to your piece as the dowels will stand out (in color) quite a bit after you've applied a finish.
Good Sources on the Web
All these points above are valid from 2x4s up to 2x10s or even bigger stock I think. I suggest you watch a video by Steve Ramsey about 'What You Need to Know About Glue | WWMM BASICS'. A great article describing all sorts of stuff that can be done with glue and how strong which bonds are, is from Mathias Wandel (woodgears.ca).
Your approach in general
While having strong bonds and sound joints makes a lot of sense, I think you should ask yourself how strong your joint really needs to be. If I understand your project correctly you're planning on putting something on top of your pedestal, which would only put pressure from the top of the piece. If that is the case, strictly speaking some nails to connect the pieces would suffice as there will be no forces exerted from the sides and the joints don't necessarily need to be that strong. This is of course not beautiful and one wouldn't do something like that for a decorative piece :)