Parts of speech are morphological or morphosyntactic classes of words. Not all languages have parts of speech, but in those which do, such as Latin or French or English, the parts of speech are distinguished based on their inflexion patterns (or lack thereof) and their allowed combinations.
(For those of us who have experience with compilers, the parts of speech are comparable to the classes of tokens recognized by the lexer, such as identifiers, numbers, operators and separators.)
For example, in Latin there are three very different patterns of inflection (verbal conjugation, nominal declension, and pronominal declension); adverbs, prepositions and conjunctions have no inflection but their allowed combinations are distinct (adverbs with adjectives or verbs, prepositions with nouns or nominal groups, conjunctions with nominal groups or sentences). Grammarians make tables with inflection patterns and allowed combinations; the cells of the table are the parts of speech.
For example, in English, we can make the following classification tree:
Does the word have an -ing form, a past tense, can it make a future tense with will? If yes, then it is an ordinary verb. (Examples: be, drink, put, see, take.)
Otherwise, can if appear in the same syntactic position as a regular verb? If yes, then it is a modal verb. (Examples: can, may, shall.)
Otherwise:
Can it determine a verb? If yes, then it is an adverb. (Examples: fast, quickly, truely, well.)
Can it function as the subject of a verb? If yes, then it is either a noun or a pronoun:
Does the word identify one particular object? If yes, it is a proper noun.
Otherwise, can it be determined by an adjective? If yes, then it is a common noun.
Otherwise, it is a pronoun. (English pronouns can also be identified by their peculiar inflection.)
Can it determine a noun? If yes, then it is either an article or an adjective or a numeral:
Can the word form degrees of comparison? (Purely morphologically speaking -- "more unique" is morphologically correct although logically silly.) If yes, it is an ordinary adjective.
Otherwise, is the word one of a class of adjectives which are required to appear with nouns used as subjects or direct objects? If yes, then it is an article or demonstrative.
Otherwise, does it express a specific number? If yes, then it is a numeral.
Many words belong to more than one of these classes. In particular the vast majority of nouns can also function as adjectives and vice-versa.
Otherwise, must the word be used immediately front of a noun or nominal group, or immediately after a verb? If yes, then it is a preposition.
Otherwise, can the word be used to link nouns, or nominal groups, or verbs, or sentences? If yes, then it is a conjunction.
Otherwise, you have found a word which cannot be classified by this decision tree. (Hint: consider interjections such as ah and oh.)
In English, verbs have a different inflexion pattern than nouns, and both have a different inflexion pattern than pronouns; unlike Latin, English makes little or no difference between nouns and adjectives (they are not really different parts of speech in English), but English has articles. (Articles work syntactically exactly like demonstrative adjectives, the difference being that a language is said to have articles if there are syntactic constructions where an article or demonstrative is absolutely required, with the label "articles" being applied to those demonstratives which have the weakest meaning.)
In languages with rich morphology the distinction between parts of speech is clear, and sentence structure is carried by morphology alone or with very little help from word order.
On the other hand, isolating language such as Mandarin have no inflection whatsoever (or almost none); in such languages the notion of "parts of speech" is much blurred, and becomes comparable to the difference between keywords and ordinary identifiers in programming languages. English is well on its way towards this; many English words can function as nouns, adjectives and verbs either completely unchanged ("they go" -- verb, "we had a go" -- noun, "all systems are go" -- adjective; or "go to a place" -- noun, "to place something" -- verb; or "have a drink" -- noun, "to drink something" -- verb) or with little change ("red" -- adjective or noun; "to redden"). In such languages with no morphology or very little morphology the distinction between parts of speech is highly attenuated, and the syntactical structure of sentences is represented by word order, much like in programming languages.
For example, in Latin "puer puellam vidit", "puellam puer vidit", "vidit puellam puer" etc. all mean "[the] boy saw [the] girl", whereas in English no other word order is possible without changing the meaning or making the utterance incomprehensible.