There are three main strategies for indicating grammatical relations in languages with free word orders. It is common for languages to have more than one of these, and to my knowledge all free word order natural languages have either case or verbal agreement.
Case refers to grammatical markers attached to nouns which indicate the noun's role in the sentence. Some languages have a very large number of cases, but in general you can expect such a language to have at least two cases: nominative and accusative, or ergative and absolutive. Here is an example from Walmajarri:
parri-ngu pa manga-Ø nyanya
boy-subj AUX girl-obj saw
'The boy saw the girl.'
parri-Ø pa nyanya manga-ngu
boy-obj AUX saw girl-subj
'The girl saw the boy.'
ngu is the ergative case marker. Walmajarri has a null absolutive case marker, shown here as
The second strategy is agreement, where markers are attached to the verb to give information about the subject and object. Depending on the language, these markers might indicate the person, number, or gender of each noun. Here's an example, again from Walmajarri:
'You two watch out for me in the north.'
Here the verb has two suffixes (actually clitics),
-pila, which mean a 1st person singular object, and a 3rd person dual subject. While it is most common for these verbal agreement markers to be attached to the verbs, in some languages they are attached to other elements in the sentence. In Walmajarri the most common sentence form actually has these markers attaching to a modal auxiliary:
ngayirta ma-rnalu majurra kang-ka-rla
NEG AUX-1plincS matches carry-IRR-PAST
'We didn't take matches.'
ma is the unmarked modal auxiliary, to which
-rnalu is attached, the marker for a 1st person plural inclusive subject. Matches is a third person singular object and so has a null marker.
The third strategy is incorporation, where a language productively forms compound words where the verb includes the object. English doesn't do this very productively - our compounds are more like individual set combinations. So in the verb babysit the object baby is incorporated, but the meaning of the compound is not obviously derived from its component parts. In incorporating languages this process happens productively with the components often keeping their normal sense. Here is an example from Nuu-chah-nulth:
'A man bought a house.'
ʔu-ʔaa-mit-ʔiš maḥt'ii čakup
Ø-buy-past-3.ind house man
'A man bought a house.'
Nuu-chah-nulth is called an obligatory incorporating language because if the object is not incorporated a dummy morpheme
ʔu must be used.
Now while incorporation is used in many languages, we have to be careful about making generalisations as each language incorporates nouns according to its own rules. Some incorporate adjectives, and some don't. Or for example, in Nahuatl an independent noun indicates a specific event, whereas an incorporated noun indicates a more general or habitual meaning:
ni-c-qua in nacatl
I-it-eat the flesh
'I eat the flesh.' [particular act]
'I eat flesh' or 'I am a flesh-eater.'
A free word order conlang could require incorporation of all objects and not use either case or agreement, a typological combination that does not exist in natlangs to my knowledge.