In the linked design (above) for the desk they use butt joints and they use screws to construct the legs. But I was wondering if it would be better if I used wood glue.
For some joints screws can be stronger than glue, but where face grain meets face grain a properly done glued joint is stronger than the wood itself, so not much need to reinforce that :-) In some cases it would be better to use both, a glued and screwed joint can be much more secure than either used alone.
So for the columns the legs rise in I'd go with glue only.
Where I would probably retain screws is on the angled braces. They would very likely be more than strong enough if simply glued in place, but no harm in reinforcing. If you want those braces to be removable though screws only of course.
The guy at Home Depot suggested I use deck screws and counter-sink them. If I go with screws, will the deck screws work just fine or should I use a different type?
Deck screws should be fine. They may be overkill in terms of size (gauge) and/or length, you could very likely use basic wood screws without the result being weakened enough to worry about, but it's rare to regret going too strong instead of the opposite!
Because you're using a fine-grained hardwood it's advisable to pre-drill for the screws.
counter-sink them
Although some woodworkers seem to be pathologically opposed to using screws in 'proper' woodworking jobs I have no issue with them myself, but, with few exceptions I don't like seeing screw heads on the finished job and they'd remain plainly visible if you just countersink them. So I'd do counterbores myself.
The small hole that the screw head hides at the bottom of could be filled with fillers of various kinds, a long-grain wooden plug or dowel (showing end grain), either to try to blend in or in a contrasting colour or grain if you want to make them more decorative. To make most of a feature of them use a turned wooden cap, AKA "mushroom buttons":
[Source: Craftparts.com, which also sells other plug types]
In addition to their decorative value these have a practical advantage if you haven't glued the respective joints. They can easily but levered from the hole, giving access to the screws should you need to do any adjustments or break the table down into its constituent parts for moving.
