What order should I add ingredients when making soup?
Goldilocks provided some very good general advice.  Just to address a few more points in the specific questions posed:

1) In what order should I saute the first veggies (for example, garlic onion and carrots) ? How long do I need to cook them for?

Garlic takes the shortest time to cook, particularly if it is minced or pressed, so it should be added last, probably only a minute or two before adding the liquid.  (You can also add some spices at this point, to bring out certain fat-soluble aromatics.)  Timing of other veggies don't matter so much.  If you want your onions to partially caramelize, start them by themselves first.  

Sauteing is about getting flavors from the fat to interact with the food and somewhat about browning reactions.  So, it doesn't matter if the veggies don't all get very cooked here.  (It's hard to say exactly how long; it depends on temperature and whether you're interested in getting anything browned or just exposing it briefly to the fat, which will still bring out flavors that the stock/broth won't.)

2) When I add the bouillon and the rest of the vegetables, should I add the longer cooking ones first, or cut them into smaller pieces? Suppose I'm using potatoes, beans, celery, and parsley. Obviously the potatoes require more time then parsley. So how should I do this? (Should I cook harder vegetables longer, or cut them into finer pieces?)

It depends on how finicky you are about the final texture of the various ingredients.  If you want them all done to perfect doneness, you can add them at staggered intervals depending on how long it takes for them to cook.  Personally, with many soups I'm okay if some things are mushy, so I often dump most ingredients in along with the stock/broth.  (Actually, to save time, I'm often chopping up things as I go, so I dump them in as I finish cutting.)  But if there's something that you feel is overdone one time, remember that and add it a little later the next time.

Herbs are a special case.  If you want their flavor integrated into the ingredients, add them early (though generally not more than 30-60 minutes before the end of cooking).  If you want a more "fresh herb" taste that stands out, add them in the last few minutes or sprinkle raw over the soup when serving.

3) When should I add the meat?

As Goldilocks said, for maximum flavor you probably want to brown the meat first, before starting anything else.  You then remove the meat and saute the vegetables in the fat leftover from the meat, while scraping the bottom of the pan to get all the nice browned bits mixed in.  Then you add the meat back in along with the liquid and the rest of the ingredients.  If you're short for time, you can also leave the meat in the pan while sauteing the veggies, though it will be less effective.  If the meat is pre-cooked (e.g., reusing roasted chicken in chicken soup/stew), you can probably just add it with the liquid.

4) If I want to thicken it with starch, when should I add it?

It depends on the starch.  Flour usually needs to cook a while so that it doesn't taste "raw" or grainy.  Other starches (like cornstarch) do not require extensive cooking, though you will need to bring to a low simmer for a few minutes to allow the starches to fully expand.  If I'm not following a specific recipe, I often make a roux-like thickener by adding some flour to the vegetables at the end of the saute phase and cook along with the remaining fat there for a few minutes.  Then add the liquid, starting with a little at first to dissolve the flour (and avoid lumps).

I usually do not thicken it completely at the beginning to avoid sticking or burning during simmering.  But this gets the thickening started, which can then be finished by adding a little more starch at the end (the last 5-10 minutes, perhaps longer if using flour or coarser meal as thickener), as needed.  Do keep in mind when adding starch to hot liquid at the end that you should begin by adding some of the liquid (or cold water/other liquid) directly to the starch to dissolve it a bit.  Then add this mixture slowly to the soup; this will help to avoid lumps.