Should the temporal indicators be in a certain order? To translate “what did you eat today at lunch?” in Chinese, I have 午饭 to translate lunch, and 今天 for today. Do they have to be located at the beginning of the sentence?


  今天午饭你吃了什么？


or can I put them in other locations, such as


  你午饭今天吃了什么？


Are those interchangeable?
The time specification should be before the verb, but you can choose whether you put it before or after the subject. There is (a little bit) more emphasis on the first word.

So you can either say 今天你吃什么了？  or 你今天吃什么了？

In case you have both a time description, a place description and explained how you did something (manner), the time should be first, then the manner and finally the place.

An example: 我   昨天  在北京     看到他 （I saw him yesterday in Beijing) 

See the Chinese Grammar Wiki for more details and some more examples.

Also, in Chinese you normally specify something from broad to narrow, general to concrete. So the year comes before the month, the month comes before the day, and so on. For example, you could say 去年八月21号上午九点. For places it is similar (first the country, then the city, than the street, ...).

In your example 午饭 can be seen as the topic of the sentence. See Wikipedia for more information about topic prominence.

With commas, your first sentence would be 今天，午饭，你吃什么了？ (I'll put the 了 at the end. Before 什么 is done a lot, but not really correct. I won't go into details about this, since it is a completely different topic). 今天，午饭 is the topic of the sentence.

You can also say this as 今天的午饭，你吃什么了？

The second sentence is not really something you can use in written language, but people might say it in oral language, but they would say it like this 你午饭，今天吃什么了？  (added a comma). It still sounds quite awkward to me and certainly isn't standard usage, but I'm pretty sure some people would say it like this and others wouldn't look strange hearing this.

(I currently have no time, I'll extend this later).